AcWing 1479. 最大子序列和
原题链接
中等
作者:
尘轩
,
2024-04-24 20:01:35
,
所有人可见
,
阅读 2
前缀和+类似单调队列思想
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 200010, INF = 0x3f3f3f3f;
int n;
int a[N], s[N];
int main() {
cin >> n;
bool flag = true;
for (int i = 1; i <= n; i++) {
cin >> a[i];
s[i] = s[i - 1] + a[i];
if (a[i] >= 0) flag = false;
}
if (flag) {
cout << 0 << " " << a[1] << " " << a[n] << endl;
return 0;
}
int res = -INF, cnt = s[0];
int l, r, u = 1;
for (int i = 1; i <= n; i++) {
if (res < s[i] - cnt) {
res = s[i] - cnt;
r = i;
l = u;
}
if (cnt > s[i]) {
cnt = s[i];
u = i + 1;
}
}
cout << res << " " << a[l] << " " << a[r] << endl;
return 0;
}