SMMR-104: Potion

#include <bits/stdc++.h>

using namespace std;
using lli = long long;
const int N = 1e6 + 10;
const int INF = 1e18;
lli dp[2][14];
lli ar[N];
int n;

int main(){

    scanf("%d", &n);

    for(int i=1;i<=n;i++) scanf("%lld", &ar[i]);

    if(n < 4){
        printf("GGWP");
        return 0;
    }

    for(int j=0;j<=4;j++)
        dp[0][j] = dp[1][j] = -INF;

    for(int i=0;i<=n;i++) dp[i][0] = 0;

    for(int i=1;i<=n;i++){
        int cur = i % 2;
        int pre = (i - 1) % 2;
        for(int j=1;j<=4;j++){
            lli a, b;
            if(j % 2 == 1) a = dp[pre][j-1] - ar[i];
            else a = dp[pre][j-1] + ar[i];
            b = dp[pre][j];
            dp[cur][j] = max(a, b);
        }
        for(int j=1;j<=4;j++)
            dp[pre][j] = -INF;
    }

    lli mx = -INF;
    for(int i=1;i<=n;i++)
        mx = max(mx, dp[i % 2][4]);

    printf("%lld\n", mx);

    return 0;
}