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;
}

Download