本文共 834 字，大约阅读时间需要 2 分钟。

连续子数组的最大和

输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 O(n).
输入
[1,-2,3,10,-4,7,2,-5]
输出
18 （3,10,-4,7,2 ）

public int FindGreatestSumOfSubArray(int[] array) {
            if (array.length==0 || array==null) {
                return 0;         }         int curSum=0;         int greatestSum=array[0];        //把数组分为前中后三段，中间段是满足要求的，那么前、后的总和一定是负        //因此从前往后累加，如果累加结果为负了，那就从下一个开始重新累加        //每一次累加之后都判断一下结果是否为最大的，把最大的保存下来，如果遇到一个负数使累加结果减少不会影响最大值         for (int i = 0; i < array.length; i++) {
                if (curSum<=0) {
                    curSum=array[i]; //记录当前最大值             }else {
                    curSum+=array[i]; //当array[i]为正数时，加上之前的最大值并更新最大值。             }             if (curSum>greatestSum) {
                    greatestSum=curSum;              }         }         return greatestSum;     }