53. Maximum Subarray最大子序和

时间:2023-12-14 10:28:32

网址: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;
}
};

53. Maximum Subarray最大子序和