dp[i][1] 表示以第 i 个元素结尾的最大子序和，dp[i][0] 表示不以 i 结尾的最大子序和。
class Solution { public: int maxSubArray(vector<int>& nums) { memset(dp, -0x3f, sizeof(dp)); for(int i = 0; i < nums.size(); ++ i) { if(i == 0) dp[i][1] = nums[i]; else { dp[i][1] = max(dp[i - 1][1] + nums[i], nums[i]); dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]); } } return max(dp[nums.size() - 1][0], dp[nums.size() - 1][1]); } static const int maxn = 3e4 + 10; int dp[maxn][2]; };
然后很明显可以用滚动数组优化，变成空间复杂度O(1)：
class Solution { public: int maxSubArray(vector<int>& nums) { memset(dp, -0x3f, sizeof(dp)); for(int i = 0; i < nums.size(); ++ i) { if(i == 0) dp[i % 2][1] = nums[i]; else { dp[i % 2][1] = max(dp[(i - 1) % 2][1] + nums[i], nums[i]); dp[i % 2][0] = max(dp[(i - 1) % 2][0], dp[(i - 1) % 2][1]); } } return max(dp[(nums.size() - 1) % 2][0], dp[(nums.size() - 1) % 2][1]); } static const int maxn = 3e4 + 10; int dp[2][2]; };