PTQMSEQ - Dãy số vòng tròn
Tác giả: RR
Ngôn ngữ: C++
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <complex>
#define FOR(i,a,b) for(int i = a; i <= b; ++i)
#define FORD(i,a,b) for(int i = a; i >= b; --i)
#define REP(i,a) for(int i = 0; i < a; ++i)
#define MP make_pair
#define PB push_back
using namespace std;
const int MN = 2000111;
long long a[MN];
int main() {
int n; scanf("%d", &n);
int x;
FOR(i,1,n) {
scanf("%d", &x);
a[i] = a[i-1] + x;
}
long long nn = 0, ln = 0;
long long res = -1000111000111000111LL;
FOR(i,1,n) {
if (i < n) res = max(res, a[i] - nn);
if (i > 1) res = max(res, a[n] - a[i-1] + ln);
ln = max(ln, a[i-1]);
nn = min(nn, a[i]);
}
cout << res << endl;
return 0;
}