leetcode-53. 最大子数组和

所有的动态规划，都要按照下面的模板解题：

理解题意

题目要我们找出和最大的连续子数组的值是多少，连续是关键字，连续很重要，不是子序列。

题目只要求返回结果，不要求得到最大的连续子数组是哪一个。这样的问题通常可以使用动态规划解决。

定义状态（定义子问题）

\(dp[i]\):表示以\(num[i]\) 结尾的连续子数组的最大和。

状态转移方程（描述子问题之间的联系）

根据状态的定义，由于\(nums[i]\)一定会被选取，并且以\(nums[i]\)结尾的连续子数组与以\(nums[i - 1]\)结尾的连续子数组只相差一个元素 \(nums[i]\)。

假设数组 nums 的值全都严格大于0，那么一定有\(dp[i] = dp[i - 1] + nums[i]\)。

可是\(dp[i - 1]\)有可能是负数，于是分类讨论：

如果\(dp[i - 1] > 0\)，那么可以把\(nums[i]\)直接接在\(dp[i - 1]\)表示的那个数组的后面，得到和更大的连续子数组；如果\(dp[i - 1] <= 0\)，那么\(nums[i]\)加上前面的数\(dp[i - 1]\)以后值不会变大。于是\(dp[i]\) 另起炉灶，此时单独的一个\(nums[i]\)的值，就是\(dp[i]\)。以上两种情况的最大值就是\(dp[i]\)的值，写出如下状态转移方程：

\[ dp[i]= \begin{cases} dp[i-1]+nums[i] & dp[i−1]>0 \\ nums[i],& dp[i−1]≤0 \\ \end{cases} \]

记为状态转移方程 1。

状态转移方程还可以这样写，反正求的是最大值，也不用分类讨论了，就这两种情况，取最大即可，因此还可以写出状态转移方程如下：

\[ dp[i] = max\left\{nums[i],dp[i-1]+nums[i]\right\} \]

记为状态转移方程 2。

思考初始值

\(dp[0]\)根据定义，只有1个数，一定以\(nums[0]\)结尾，因此\(dp[0] = nums[0]\)。

思考输出

这里状态的定义不是题目中的问题的定义，不能直接将最后一个状态返回回去。

这个问题的输出是把所有的\(dp[0]、dp[1]、……、dp[n - 1]\)都看一遍，取最大值。

编码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> sum = vector(nums.size() + 1, 0);
        int result = nums[0];
        for (int i = 1; i <= nums.size(); i++)
        {
            sum[i] = max(nums[i-1] + sum[i-1], nums[i-1]);
            result = max(result, sum[i]);
        }
        return result;
    }
};