Cod sursă (job #333616)

#include <fstream>
#include <algorithm>
#include <cstring>

using namespace std;

const int NMAX = 2005;

int v[NMAX];
int all_vals[NMAX];

int dp[NMAX][NMAX];

int frecv[NMAX];

int main()
{
    ifstream cin("s2c.in");
    ofstream cout("s2c.out");

    int t = 0;
    cin >> t;

    while (t --) {
        int n = 0;
        cin >> n;

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

        sort(all_vals + 1, all_vals + n + 1);

        int sz = 0;
        sz = unique(all_vals + 1, all_vals + n + 1) - all_vals - 1;

        for (int i = 1; i <= n; ++ i)
            v[i] = lower_bound(all_vals + 1, all_vals + sz + 1, v[i]) - all_vals;

        int best = 0;
        for (int i = 1; i <= n; ++ i) {
            //Initializam vectorul de frecventa
            memset(frecv, 0, sizeof frecv);

            for (int j = 1; j < i; ++ j)
                frecv[v[j]] = dp[j][i];
            for (int j = 1; j <= n; ++ j)
                if (frecv[j - 1] > frecv[j])
                    frecv[j] = frecv[j - 1];

            for (int j = i + 1; j <= n; ++ j) {
                dp[i][j] = 1 + frecv[v[j] - 1];
                if (dp[i][j] > best)
                    best = dp[i][j];
            }
        }

        cout << 1 + best << '\n';
    }

    cin.close();
    cout.close();
    return 0;
}