普通数组#中等#最大子数组和

前文

给你一个整数数组nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

正文

动态规划的要点在于：

• 思考是否能否分解小问题
• 列出方程式（状态转移方程）
• 考虑初始条件从小到大编写代码（即逐渐靠近方程中需要的值， 大多数情况都是需要最后一个状态，由之前的状态推导而来，这体现在编码中能避免重复计算(记忆化)）
• 考虑边界
• 考虑特殊情况
• 根据给定条件挑几个极端条件，比如空集合等

class Solution {
public:
    int maxSubArray(vector<int>& nums) {

    }
};

解法1 动态规划

class Solution {
public:
    int maxSubArray(vector<int>& nums) {

        if (nums.size() == 1) {
            return nums[0];
        }
        vector<int> sum = nums;
        int max = nums[0];
        // 1, -1, 2, 3, -1
        for (auto i = 1; i < nums.size(); ++i) {
            if (sum[i-1] + nums[i] > nums[i]) {
                sum[i] = sum[i-1] + nums[i];
            } else {
                sum[i] = nums[i];
            }
            if (sum[i] > max)
                max = sum[i];
        }

        return max;
    }
};

解题重点在于最大子数组是连续的，所以使用sum[i] = max(sum[i-1] + nums[i], nums[i])和用一个max变量记录历史最大值。

因此此题的动态规划可以这样思考：

假设有数组{2, -1, 3, 10, -1, 2}，注意此时max已经设为2，因为是连续子数组， 比较{2, -1}和{-1}的大小即可，依次类推，比较{2, -1, 3}和{3}的大小，比较{3}和{3， 10}的大小， 依次比较完，注意比较完大小会更新max的值。