教做年糕博客网站深圳百度关键字优化

53. 最大子序和 - 力扣（LeetCode）

直接求解

其实就是前缀和的思路，当某段前缀和小于等于0的时候，这一段只会对后面产生负作用，所以应该舍弃掉这一段，重新开始。

class Solution {
public:int maxSubArray(vector<int>& nums) {if(nums.empty()) return 0;int res = nums[0];int sum = 0;//累加和for(auto c : nums){if(sum > 0)  sum += c;else    sum  = c;//累加和 <= 0，再累加下去只会对后面产生负作用res = max(res, sum);}return res;}
};

动态规划

$$f[i]=max(f[i-1]+nums[i],nums[i])$$

class Solution {
public:int maxSubArray(vector<int>& nums) {if(nums.empty()) return 0;int pre = 0, res = nums[0];for(auto c : nums){pre = max(pre + c, c);res = max(pre, res);}return res;}
};