AcWing 55. 连续子数组的最大和
原题链接
简单
作者:
二十七杯酒
,
2020-12-30 11:50:56
,
所有人可见
,
阅读 518
连续子数组的最大和(备忘)
C++ 代码
class Solution {
public:
int maxSubArray(vector<int>& nums) {
if(nums.empty())return 0;
int sum = nums[0], Max_count = nums[0];
for(int i = 1; i < nums.size(); i ++ ){
if(sum < 0) sum = nums[i];
else sum += nums[i];
Max_count = max(sum, Max_count);
}
return Max_count;
}
};
//dp
class Solution {
public:
int maxSubArray(vector<int>& nums) {
//dp[i]表示以nums[i]结尾的连续子数组的最大和
int pre = 0, max_ = nums[0];//pre代表dp[i - 1]
int cur;//cur代表dp[i]
//if(dp[i - 1] > 0) dp[i] = nums[i] + dp[i - 1]
//else dp[i] = nums[i];
for(int i = 0; i < nums.size(); i ++ ){
cur = nums[i];
if(pre > 0) cur += pre;
max_ = max(cur, max_);
pre = cur;
}
return max_;
}
};