每日一题：求连续子数组的最大和

题目：

输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。

解析：

刚拿到这道题时，觉得这道题很简单，但提交了好几次都失败，脑子就有点乱。随后翻看题解发现这道题好ta **的nb，我是真的fw。

思路：

我们要求连续子数组的和，刚开始我想的是从前往后遍历，搞两个变量一个sum，一个cur，sum来记录最大子数组和，cur来记录目前走到的前缀和，遇到负数就清空cur，然后继续遍历。但问题就来了：遇到一个负数，但是如果负数后面有个更大的正数例如：（【1，-2, ，3,10，-4,7,2，-5】）这个数组当遇到-4，其实它后面加了更大的数所以和会更大。

所以得换个思路：我们依旧从前往后遍历，然后先判断上次加完的ret是否为负，若为负则跳过原来节点把ret设为当前节点的值（先不用管这次的为正还是负，判断留在下一次），如果为正，则继续把当前节点加入ret中，然后把ret与sum比较取最大值。进行下一次循环。

代码实现：

int FindGreatestSumOfSubArray(vector<int>& array) {
        // write code here
        if(array.size()==0)
            return 0;
        int sum=array[0],ret=array[0];
        for(int i=1;i<array.size();i++)
        {
            if(ret<0)
                ret=array[i];
            else
                ret+=array[i];
            sum=max(sum,ret);
        }
        return sum;
    }
};