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

第三十九题 算法QAQ

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        // 暴力 多层循环 每一次都扫到尾来找最大值
        // 因为有负数，所以不知道是否要往后加。其实可以知道，如果加上负数，数字小于0了，那么显然就不要加了
        int temp=0,max=-100000;
        // 从前向后遍历
        for(int i =0;i<array.size();i++)
        {
            // 如果说 加上了数组中的值，整体变负的了，就说明前面这一串 和后面的数字肯定是分开来的
            // 那么就让temp重新开始统计往后的数字
            if(temp<0)
                temp=array[i];
            // 如果说还是正的，那么前面那一串都是有用的，把后面的数字应该加上去
            // 比如说序列式 1,2.3.-5,10
            // 访问完123 现在temp是6，当访问完-5，temp成了1，说明前四个数字加起来还是正的，当向后访问的时候还是需要的
            // 1+10 最后结果得到是11。
            
            // 假如说是 1,2,3,-5,2 这样前面四个数是1，加上2得到了是3.但是因为前面max都是保存下来的，所以结果也不会错
            else
                temp += array[i];
            max=temp>max?temp:max;
        }
        return max;
    }
};