LeetCode #53：Maximum Subarray(最大子数组和)

题目描述

本题是一个经典的动态规划问题。需要注意的是解题时将 dp[i] 定义为数组 nums 中以 num[i] 结尾的最大连续子串和，最终不能直接返回 dp[n-1]，因为给定数组的最大连续子数组不一定以该数组的最后一个数结尾。这里采用一个额外的 res 变量来记录最大值。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        
        int n = nums.size();
        vector<int> dp(n, -10e4 - 1); //dp[i]定义为数组nums中以num[i]结尾的最大连续子串和

        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(dp[i], res); 
        }

        return res; //不能直接返回dp[n-1]，不符合题意，最大连续子数组不一定以最后一个数结尾
    }
};