AcWing 55. 连续子数组的最大和(贪心和DP)
原题链接
简单
作者:
林夕丶
,
2022-02-13 15:08:50
,
所有人可见
,
阅读 1000
class Solution {
public:
// dp: f[i] 表示前i项中 以i结尾的连续子序列的最大和
// 因为我们的f[i] 仅仅是表示以i结尾的,所以要对每一个 f[i] 求max得到最大值
// 这里发现f[i] 只依赖于 f[i - 1], 所以可以用prev 来表示f[i - 1]
int maxSubArray(vector<int>& nums) {
// return f2(nums);
int sub = 0, res = -1e9;
int prev = 0;
for(const auto num: nums) {
// prev = max(prev, 0) + num; 即 f[i] = max(f[i - 1] + num, num);
prev = max(prev + num, num);
res = max(prev, res) ;
}
return res ;
}
//贪心 :将 整一个数组 分成一个个 连续的和为正整数的数组
// 然后 不断枚举即可
int f2(vector<int>& nums) /
{
int sub = 0, res = -1e9;
for(const auto num: nums) {
sub += num; // sub 不断累加
res = max(sub, res);
if(sub < 0) sub = 0; //变成 负数的时候 就断开
}
return res;
}
};