1699D - Almost Triple Deletions - CodeForces Solution

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 5e3 + 5;

int n;
int a[MAXN];
int dp[MAXN];
int cnt[MAXN];

void solve() {
    cin >> n;

    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    for(int i = 0; i <= n + 1; ++i) {
        cnt[i] = dp[i] = 0;
    }

    for(int i = 0; i <= n; ++i) {
        if(i > 0 && dp[i] == 0) {
            continue;
        }

        int currmax = 0;

        for(int j = 1; j <= n; ++j) {
            cnt[a[j]] = 0;
        }

        for(int j = i + 1; j <= n + 1; ++j) {
            if(currmax * 2 <= (j - i) && (i - j + 1) % 2 == 0) {
                if(i == 0 || j == (n + 1) || a[i] == a[j]) {
                    dp[j] = max(dp[j], dp[i] + 1);
                }
            }
            ++cnt[a[j]];
            currmax = max(currmax, cnt[a[j]]);
        }
    }

    cout << dp[n + 1] - 1 << endl;
}

int main() {
    int t;
    cin >> t;
    while(t--) solve();
    return 0;
}