PROG-T1093: Book

#include <bits/stdc++.h>
using namespace std;

typedef long long lli;

const int N = 2000;

int n, arr[N + 1], dp[N + 1][N + 1];

int dpTD(int i, int s){
    if(i == n + 1){
        return s == 0 ? 0 : -1e9;
    }
    if(dp[i][s] != -2e9){
        return dp[i][s];
    }
    int mx = arr[i] + dpTD(i + 1, s + 1);
    if(s >= 2){
        mx = max(mx, -arr[i] + dpTD(i + 1, s - 2));
    } else if(s == 0){
        mx = max(mx, dpTD(i + 1, s));
    }
    return dp[i][s] = mx;
}

int main(){

    scanf("%d", &n);
    for(int i = 1; i <= n; ++i){
        scanf("%d", &arr[i]);
    }
    for(int i = 1; i <= n; ++i){
        for(int s = 0; s <= n; ++s){
            dp[i][s] = -2e9;
        }
    }
    cout << dpTD(1, 0);

    return 0;
}