动态规划

• dp[i]保存连续和，理解dp[i]=max(dp[i-1]+array[i],array[i])
• 如果dp[i-1]+array[i]<array[i]，原来的起点到array[i]之间连续和使得array[i]更小，从array[i]作为起点会更大
• 当dp[i]=array[i]时，更新起点，从array[i]开始计算。
• 更本质地来说从找出最大和的起点，dp[i]保存的从某个起点开始的连续和。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型
     */
    int FindGreatestSumOfSubArray(vector<int>& array) {
        // write code here
        int dp[array.size()];
        dp[0]=array[0];
        int max_val=dp[0];
        for(int i=1;i<array.size();i++)
        {
            dp[i]=max(array[i],dp[i-1]+array[i]);
            if(max_val<dp[i])
            {
                max_val=dp[i];
            }
        }
        return max_val;
    }
};

动态规划优化

• 不需要回溯变量因此只用一个变量保存值，另外一个变量记录最大值

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型
     */
    int FindGreatestSumOfSubArray(vector<int>& array) {
        // write code here
        int sum=array[0];
        int max_val=sum;
        for(int i=1;i<array.size();i++)
        {
            sum=max(array[i],sum+array[i]);
            max_val=max(sum,max_val);
        }
        return max_val;
    }
};