【作业】返回一个整形数组中最大子数组地和

一、不考虑时间复杂度

 1 public static void main(String[] args)
 2     {
 3         int LONG=20;//数量
 4         int FANWEI=10;//   n  :    -n   ~   +n
 5         Scanner input=new Scanner(System.in);
 6         int [] num=new int[LONG];
 7         int []kuai=new int[LONG];
 8         for(int k=0;k<LONG;k++)
 9         {
10             num[k]=(int)(1+Math.random()*FANWEI*2)-FANWEI;
11             System.out.println(num[k]);
12         }
13         System.out.println("/////////////////////////////////////////");
14         //int [] num= {1,8,5,-6,9,-7,-9,4,5,-9,-3,4,-5,4};
15         int i=0,t=0;
16         int sum=0,max=0,aMax=num[0];
17         //从第一个开始加直到最大，中途记录
18         for(i=0;i<num.length;i++)//起始
19         {
20             t=0;
21             max=num[t];//赋初值
22             for(sum=num[t+i];t<num.length-i-1;t++)//加
23             {
24                 if(max<=sum)//比较，记录最大
25                 {
26                     max=sum;
27                     
28                 }
29                 //System.out.println(sum);
30                 sum=sum+num[t+1+i];
31                 
32                 
33                 
34             }
35             if(aMax<=max)
36             {
37                 aMax=max;
38             }
39         
40         
41             //System.out.println("");
42             System.out.println(max);
43             
44         }
45 
46         
47         System.out.println("END"+aMax);
48         
49 
50     }

Code_1

首先随机生成一个数组

1.从0开始相加，max记录这一过程中的最大值

2.从1开始相加，同上

3.从2开始

。

aMax记录每一次遍历结束后max的最大值

最终aMax为所求最大值

时间复杂度为o(n^2)

二、如何让时间复杂度为o(n)的思考（未果）

无论如何一一比较大小将数组遍历两遍是必须的，那么就必须去思考一个算法，使得不需要比较所有的的整数。

然而好多同学的算法只是将遍历这一过程复杂化并没有起到解决时间复杂度的问题。

有人提出假定最大的子数组一定包含最大的整数，被我否定了（举例：1、1、1、1、1、1、1、1、1、1、1、1、-8、-9、-5、-7、-7、-9、9。9为最大，但最大子数组一定为前12个1组成的）

唯一有建设性的想法是将数组分块，将正数和负数合并为一个块，但是在之后如何计算仍是问题

10、-5、10、-5、-1000000000000、100

最大的块仍然不一定被最大的子数组包含

老师提出利用离散中学到的图的算法，去思考两个块相连是否会使总值变大，如果会，那么便相加。

但是虽然看起来最终可以得出结果，但是仍然需要很多遍历（因为不一定包含最大）

思考无果，不想去看正确答案，，，再想想吧