我没有实现时间复杂度为O(n)的算法。
思路:从第一数开始,onelist[0];onelist[0]+onelist[1];这样依次推算出每个子数组的sum值。和max进行比较。最后得到max值。
这里需要确定一个起始节点,最开始是onelist[0]为起始节点。一直加到onelist.length。 然后从onelist[1]一直加到onelist.length。
import java.util.Scanner; public class Test { public static void main(String [] args) { Scanner sc=new Scanner (System.in); System.out.println("请确定数组的长度:"); int n=sc.nextInt(); //-----------------输入一个数组 float [] onelist = new float [n]; System.out.println("请输入数组内的数字:"); for(int i=0;i<n;i++) { float num=sc.nextFloat(); onelist[i]=num; } //-------------------------------------------- float max=onelist[0];//-----------初始化max的值 for(int a=0;a<onelist.length;a++)//------确定起始节点 { for(int b=a;b<=onelist.length;b++)//--------确定终止节点 { float sum=0; for(int c=a;c<b;c++)//---------起点到终点的和值 { sum=sum+onelist[c]; if(max<sum) { max=sum; } } } } System.out.println("子数组最大值为:"+max); } }
请确定数组的长度: 4 请输入数组内的数字: -10 -8 -4 -1 子数组最大值为:-1.0
输入一个整形数组,数组里有正数也有负数。 数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。 求所有子数组的和的最大值。要求时间复杂度为O(n)
原文:https://www.cnblogs.com/birdmmxx/p/10500207.html