AcWing 1479. 最大子序列和
原题链接
中等
作者:
sy123
,
2021-01-04 00:56:45
,
所有人可见
,
阅读 497
#include <iostream>
using namespace std;
const int N = 10010;
typedef long long LL;
int n;
int a[N];
LL dp[N];//dp[i]代表以i结尾的连续子列和最大值
int Left[N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
LL res = -1, l, r;
for (int i = 1; i <= n; i ++ )
{
dp[i]=a[i];
Left[i]=i;
//dp[i-1]+a[i]>=dp[i]因为则选择 i 更小的解,比如a[3]=0,a[4]=5,就得把3包括
if(dp[i-1]+a[i]>=dp[i]&&i>1){ //i>1才行,不然Left[1]就等于0了
dp[i]=dp[i-1]+a[i];
Left[i]=Left[i-1];
}
if(dp[i]>res){
res=dp[i];
l=a[Left[i]];
r=a[i];
}
}
if (res < 0) res = 0, l = a[1], r = a[n];
cout << res << ' ' << l << ' ' << r << endl;
return 0;
}