题目:返回一个整数数组中最大子数组的和。

题目要求：

1.输入一个整形数组，数组里有正数也有负数。

2.数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。

3.求所有子数组的和的最大值。要求时间复杂度为O(n)

设计思想：首先我们需要知道子数组是是连续的几个量的和，所以必须要在连续的基础上进行相加，在编写过程中最大的问题就是 如何将这些子数组进行求值，并对其进行比较，由于子数组数目较多，如果挨个都算出来的话时间复杂度较高，所以必须想一个较好的办法，根据上课期间同学所讲思路的启发可以根据正负数的判断来处理这些问题，当一个数是负数时，他与其他数相加肯定不可能是最大子数组了。当然这就必须设计一个累加的值，和一记录最大的值，当累加值为符时就将数组的值赋值给他，其他情况便对数组中的值进行累加，并与所记录的最大值进行比较，并更新最大值。

出现的问题：

1.刚开始编写的时候只考虑到一个累加的问题，认为只有正数的累加才会最大，所以做的就只有正数的子数组。

解决方案：对每一次累加都进行判断，若累加后不小于零就继续向后进行累加。并不断地进行比较，更新最大值的情况

2.由于没有仔细考虑关于负数的情况，在最初的时候就考虑为都存在正数的情况，导致当数组全部为负数时无法处理。

解决方案：首先将数组中的值给最大值，并当累加值小于0时就不在累加，而是将数组的值赋值给累加值，并将累加值与最大值进行比较。这样当数组为纯负数的时候就相当于对数组中的值进行比较。另外需要注意的一个小问题就是必须将最大值赋值为数组的第一个值，否则会导致都是负数时最大值等于初值0了。

程序源代码：

1 package test; 2  3 import java.util.Scanner; 4 /* 5  * 求子数组的最大值 6  */ 7 public class shuzu { 8 static Scanner in = new Scanner(System.in); 9     public static void main(String[] args) {10         // TODO 自动生成的方法存根11         int num[] = new int[100];12         int n;13         int sum = 0;14         int value = 0;15         16         System.out.println("输入数组的个数");17         n = in.nextInt();18         System.out.println("输入数组中的值");19         for(int i = 0;i < n;i++)20         {21             num[i] = in.nextInt();22         }23         sum = num[0];24         25         26         27         for(int i = 0;i < n;i++)28         {29             if (value <= 0) {30                 value = num[i];   //当用于记录的值小于等于0时就无需对其进行相加了，此时就等于下一个值31             }else {32                 value += num[i];  //当value的值仍大于0时就继续相加33             }34             35             if (sum < value) {    //用sum等于子数组的最大值，若value的值大于sum的值，则将value赋值给sum36                 sum = value;37             }38         }39         40         System.out.println("最大值为：" + sum);41 42     }43 44 }

 

结果截图：

              

总结：这个问题其实并不简单，对于子数组的求值处理就是一个很大的问题，如果使用循环将所有的子数组都求出来在进行比较也确实可行，但是所需要处理的数据就费城大了，并且还需要重新的建立数组来存储子数组的和 当然这是最直接也是较为容易想到的方法，只不过比较繁琐。刚开始没办法我也是这样做的但是在处理方面也出现了问题导致无法实现，最终在同学的启发及查阅了资料后才找到了这个方法。