AcWing 1479. 最大子序列和(dp简洁代码,边界与初始状态)
原题链接
中等
作者:
小念
,
2022-02-24 15:10:32
,
所有人可见
,
阅读 184
#include <iostream>
#include <algorithm>
using namespace std;
int a[10010];
int f[10010];
int main()
{
int n;
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
//dp
f[0] = -1;
/*
这里是要保证在dp到第一个数的时候,我们仍然会更新起点curbegin,
因为一开始我们并没有给curbegin, b, e赋初值,
这样下面用curbegin更新答案的时候就不会出现错误。
当然,如果我们一开始就给curbegin赋值为1,也是可以的,那么f[0]就不用初始化
*/
int ans = -2e9, curbegin, b, e; //curbegin当前字串的起点 be为答案起点和终点
// ans = -2e9 保证了答案一定会被更新
for(int i = 1; i <= n; i ++)
{
f[i] = max(0, f[i - 1]) + a[i];
if(f[i - 1] < 0) curbegin = i;//不能等于是因为确保左边界尽可能小
if(ans < f[i]) ans = f[i], b = curbegin, e = i;//更新答案,不能等于原因同上
}
if(ans < 0) ans = 0, b = 1, e = n;//答案为负数,说明序列全为负数
cout << ans << ' ' << a[b] << ' ' << a[e] << endl;
return 0;
}