LeetCode题解——42.连续子数组的最大和（动态规划思想）

题目地址：剑指 Offer 42. 连续子数组的最大和 - 力扣（LeetCode）

一.解题思路 

在这道题中，数组连续是一个很重要的信息。我们可以创建一个数组用于记录每一位对应的最大值。

所谓每一位的最大值，意思就是以这一位为结尾的数组的最大值。那么我们可以利用动态规划的思想完成解题。

因为题目要求连续，所以当前位的最大值要么是与上一位最大值之和，要么就是本身的值。

画图举例说明一下：

 从下标0处出发，该下标处没有前一位，因此-2所对应最大值即本身。

 下标1对应值为1，与前一位最大值-2相加为-1，是小于本身值的，因此下标1处最大值为1。

 同理，下标2处: -3 + 1 = -2 > -3，因此最大值为-2。

按上述推导，我们在最大值数组中找到的最大值即是答案。

二.代码实现

这份代码中，并没有使用最大值数组。因为实际上我们只需记录前一位存储的最大值以及目前为止的最大值。

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

每名程序员都是作家——Sercan Leylek

如有错误，敬请斧正