题目描述

原题链接：53. 最大子数组和

解题思路

目标是找到连续的一组求和最大的子序列

暴力方法

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = INT_MIN;
        for(int i = 0; i < nums.size(); i++) {
            int count = 0;
            for(int j = i; j < nums.size(); j++) {      // j从i开始，可以保证nums.size()=1时情况和有多个负数，仅有一个正数此时正数为最大值的情况
                count += nums[j];
                res = max(res, count);
            }
        }
        return res;
    }
};

会超时

贪心算法
当后一个数是负，但后两个数是正时，有可能相加后数值会更大。例如，[0, -1, 2]，由于序列为非递增或递减序列，因此不能用双指针的方式进行求解。

而我们的目标是求和最大，当负数越来越多时，和才会变小。而当后面负数整体值小，而正数值大时，和才会变大。因此我们的一个判断指标可以是求和此时是否为0。当求和不为0时，向后遍历继续相加。当求和为0时，重新更新求和变量。

当相加为0时，若后续为正数，没有这个负数更好；若后续为负数时，越加只会越小。 因此，以count是否为0作为判定条件。

局部最优解：当连续和不为负数时，继续相加，找到最大连续和。当连续和为负数时，更新下一个起始位置开始相加。

全局最优解：找到整体的最大连续和。

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

（3）动态规划

• 动态规划五步曲：

（1）dp[i]含义： 以nums[i]结尾的子序列，所具有的最大数组之和。

（2）递推公式： dp[i] = max(dp[i - 1] + nums[i], nums[i])，下一步选择有两种情况。一种是当前的加上之前的结果，若当前的情况加上之前的总和会更小，则不加上之前情况，从当前情况重新开始。如果相加后大于当前情况，则进行相加。

（3）dp数组含义： dp[0] = nums[0]

（4）遍历顺序： 从小到大。

（5）举例：

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

参考文章：#53. 最大子序和