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

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        if(array.empty()) return 0;
        int maxNum = array[0];
        int maxSubArray = array[0];
        for(int i=0; i < array.size() ; )
        {
            if(maxSubArray > maxNum)
            {
                maxNum = maxSubArray;
            }
            if(maxSubArray > 0)
            {
                ++i;
                maxSubArray += array[i];
            }
            else
            {
                i++;
                if(i < array.size())
                {
                     maxSubArray = array[i];
                }
            }
        }
        return maxNum;
    }
};

从头到尾逐个累加数组中的每个数字，初始化和为0；（nCurrSum=0，nGreatestNum=int.MinValue）

定义两个变量：“累加子数组和”和“最大子数组和”，第一步把数组中的第一个数字赋值给他们，然后从第二个数字开始累加，累加值放入“累加子数组和”。

1.如果当前“累加子数组和”小于0，那抛弃前面的“累加子数组和”，从下一个数字开始重新累加，“最大子数组和”的值不更新。

2.如果当前“累加子数组和”大于0，再让当前“累加子数组和”和当前的“最大子数组和”进行比较。

       2.1如果当前“累加子数组和”大于当前“最大子数组和”，则更新“最大子数组和”的值为“累加子数组和”的值。

       2.2如果当前“累加子数组和”小于当前“最大子数组和”，“最大子数组和”的值不更新。

3.再加入数组中的下一个值，“累加子数组和”进入下一轮的累加，“最大子数组和”也进入下一轮的更新。知道数组中所有值都累加完毕。