网址:https://leetcode.com/problems/maximum-subarray/submissions/
很简单的动态规划
我们可以把 dp[i] 表示为index为 i 的位置上的Maximum
容易得出,dp[i] = max( nums[i] , dp[i-1] + nums[i] )
最后再把dp数组转化为两个变量之间的关系,可以减少内存开销!
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int ans = nums[];
int sum = ;
int last_sum = nums[];
for(int i=; i<nums.size(); i++){
sum = max(nums[i], last_sum+nums[i]);
last_sum = sum;
ans = max(ans, sum);
}
return ans;
}
};