动态规划：面试题42. 连续子数组的最大和

面试题42. 连续子数组的最大和

题目要求：

 解题思路：

 1. 定义子问题：

　　dp[i] 为下标以 num[i] 结尾的数组字段 元素最大最短和，i表示子段到当前i位置 i；

2. 寻找关系式：

　　只有一个元素：dp[0] = num[0];

　　两个元素：dp[i] 为num[0], num[1], num[0]+num[1]; 

　　三个元素时：考虑前三个元素，如何求其最⼤大⼦子段和？还是分为两种情况讨论，第三个元素在最后的字串串内吗？
　　　　若第三个元素也包含在最后的字串串内，则dp[2] = max(dp[1]+num[2] , num[2]) ;

　　所以转移方程为：dp[i] = max(dp[i-1] + num[i],  num[i] ) ;

3. 初始值：

　　dp[0] = nums[0]；
　　dp[1] = max(dp[0]+num[1] , num[1]) ；

class Solution {
public:
    int maxSubArray(vector<int>& nums) 
    {
        int len = nums.size();
        if (len < 1)
        {
            return 0;
        }
        int* dp = new int[len]; 
        //int[] dp = new int[len]  //不支持
        dp[0] = nums[0];
        int max = dp[0];
        for (int i=1; i<len; i++)
        {
            dp[i] = std::max(dp[i-1] + nums[i],  nums[i]);
            if (dp[i] > max)
            {
                max = dp[i];
            }
        }
        return max;
    }
};

优化：在原数组的基础上进行更改。

class Solution {
public:
    int maxSubArray(vector<int>& nums) 
    {
        int len = nums.size();
        if (len < 1)
        {
            return 0;
        }
        //int* dp = new int[len]; 
        //int[] dp = new int[len]  //不支持
        //dp[0] = nums[0];
        int max = nums[0];
        for (int i=1; i<len; i++)
        {
            //dp[i] = std::max(dp[i-1] + nums[i],  nums[i]);
            if (nums[i-1] > 0)
            {
                nums[i] += nums[i-1];
            }
            if (nums[i] > max)
            {
                max = nums[i];
            }
        }

        return max;
    }
};