13398번: 연속합 2

https://www.acmicpc.net/problem/13398


O(n)

최대연속부분합을 응용한다.
p: 최대연속부분합
q: 중간 1개를 제외한 최대연속부분합

#include<cstdio>
#include<algorithm>
using namespace std;
int p = -1e9, q, n, x, r = -1e9;
int main() {
    for (scanf("%d", &n); n--;) {
        scanf("%d", &x);
        q = max(p, q + x);
        p = max(p + x, x);
        r = max({ r,p,q });
    }
    printf("%d", r);
    return 0;
}