Subsequence Reversal

#include <bits/stdc++.h>

using namespace std;

const int N = 50 + 9;

int dp[N][N][N][N], A[N];

int Go (int l, int r, int mn, int mx) {
    if (dp[l][r][mn][mx] != -1)
        return dp[l][r][mn][mx];
    if (l > r)
        return 0;
    if (l == r)
        return A[l] >= mn && A[l] <= mx;
    int ret = 0;
    ret = max (ret, max (Go (l + 1, r, mn, mx), Go (l, r - 1, mn, mx)));
    if (A[l] >= mn && A[l] <= mx) {
        ret = max (ret, 1 + Go (l + 1, r, A[l], mx));
        ret = max (ret, 1 + Go (l + 1, r - 1, mn, A[l]));
    }
    if (A[r] >= mn && A[r] <= mx) {
        ret = max (ret, 1 + Go (l, r - 1, mn, A[r]));
        ret = max (ret, 1 + Go (l + 1, r - 1, A[r], mx));
    }
    ret = max (ret, Go (l + 1, r - 1, mn, mx));
    if (A[r] >= mn && A[l] <= mx && A[r] <= A[l])
        ret = max (ret, 2 + Go (l + 1, r - 1, A[r], A[l]));
    return dp[l][r][mn][mx] = ret;
}

int main () {
    freopen ("subrev.in", "r", stdin);
    freopen ("subrev.out", "w", stdout);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> A[i];
    memset (dp, -1, sizeof (dp));
    cout << Go (1, n, 1, 50) << "\n";
    return 0;
}