剑指offer30连续子数组的最大和

#剑指offer30
牛客题霸参考
1、动态规划
F[i]:表示以i位置结尾的连续子数组的最大和
状态方程：F[i]=max{F[i-1]+array[i],array[i]}
时间复杂度：O(n) 空间复杂度O(n)
个人代码参考

 //动态规划
    //F[i]:表示以i位置结尾的连续子数组的最大和
    //状态方程：F[i]=max{F[i-1]+array[i],array[i]}
    int FindGreatestSumOfSubArray(vector<int> array) {
        vector<int>F(array.size(),0);
        F[0]=array[0];
        int ret=F[0]; //记录F[]中最大值，即以记录以某k位置的连续子数组和的最大值
        for(int i=1;i<array.size();i++)
        {
            F[i]=max(F[i-1]+array[i],array[i]);
            ret=max(ret,F[i]);
        }
        return ret;
    }

2、空间优化
时间复杂度：O(n) 空间复杂度O(1)
个人代码参考

class Solution {
public:
//动态规划
//F[i]:表示以i位置结尾的连续子数组的最大和
//状态方程：F[i]=max{F[i-1]+array[i],array[i]}
//空间优化：
//实际上并不需要保存所有以i位置结尾的连续子数组的最大和
//因为:
//1、最终所求最大和的那个连续数组结尾位置的数一定大于0，
//即以小于0元素为结尾的连续数组对结果没贡献
//2、求以k位置元素结尾连续数组最大和时，前面的以(<k位置结尾的)连续数组，
//实际只需要是前面最大的那个最大和(连续数组)，以及该连续数组结尾与k之间的累加值
    int FindGreatestSumOfSubArray(vector<int> array) {
        int ret=0; //记录连续子数组最大值
        int sum=0; //记录上一个最大的（连续子数组的）最大和到当前元素的累加值
        int index=0;
        int Max=array[0];
        while(index<array.size()&&array[index]<0)//找第一个最大和，显然是第一个大于零的元素
        {
            Max=array[index]>Max?array[index]:Max; //顺便找到其中的最大值
            ++index;
        }
        if(index==array.size()) //若全是小于0的元素，则返回最大值
            return Max;
        ret=array[index];//第一个大于零的元素，显然就是第一个最大和
        ++index;
        for(int i=index;i<array.size();i++) 
        {
            sum+=array[i];//累加上一个最大和到当前元素
            if(sum>0) //上一个最大和连续数组的结尾累加到当前元素的和>0,说明有了贡献值
            {         //以当前元素结尾的连续数组最大和肯定大于之前的最大和了
                ret=max(ret+sum,array[i]);//以当前元素结尾的连续数组最大和的状态方程
                sum=0; //更新最大和后重新累加
            }
        }
        return ret;
    }
};