题解 | #连续子数组的最大和#

题目：连续子数组的最大和

描述：输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n).

示例1：输入：[1,-2,3,10,-4,7,2,-5]，返回值：18

说明：输入的数组为{1,-2,3,10,-4,7,2,-5}，和最大的子数组为{3,10,-4,7,2}，因此输出为该子数组的和18。

解法一：

思路分析：首先设置两个指针变量i和j，设置一个max的int类型，将array[]数组中的第一个值确定为max对象，设置一个count对象不断进行循环判断，并通过count值与max值的相互比较，最终得到结果值。

实例分析：[1,-2,3,10,-4,7,2,-5]

将j指针代表的所有值，一直进行累加，当碰到负数时，要进行判断max > count，如果大于max还是max值，如果不大于将count值赋予max。通过循环i和j不断进行判断，最终得到结果值。在下表中将max简写为m，count简写为c。

第一次循环：

……

以此类推，详细推导过程就不进行书写，直接推导答案的那一次

其最大值为18。

具体C++代码如下所示：

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        int len = array.size();
        if(len == 0)
            return 0;
        if(len == 1)
            return array[0];
        int max = array[0];//首先定义第一个元素为最大值
        for(int i= 0;i < len;i++){
            int count = array[i];
            for(int j = i+1;j < len;j++){
                if(array[j] < 0){
                    max = max > count ? max:count;
                }
                count += array[j];
            }
            max = max > count ? max:count;
        }
        return max;
    }
};

解法二：
    思路分析：经过上面的分析，我们可以得到一个结论，就是，当下标为i时，先将max与下标为i的值加上，如果为负数的话，显然以下标i开始的元素毫无用处。

具体思路分析:

由上表可知，因为1和-2相加的结果为-1，所以应该很容易得出，从1开始，是不正确的，第二个元素为-2，直接出现负数的话，直接将其去掉，一直往上类推。进行循环判断，即可得到最终结果。

其java代码如下所示：

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int max = array[0];
        int len = array.length;
        for (int i = 1; i < len; i++) {
            array[i] += array[i - 1] > 0 ? array[i - 1] : 0;
            max = Math.max(max, array[i]);
        }
        return max;
    }
}