Cod sursă (job #258022)

#include <bits/stdc++.h>
#define maxN 2005
#define maxVal 30000
#define lsb(x) ((x)&(-x))
using namespace std;
int T,n,i,j,sol,v[maxN];
int nxt[maxN],x[maxVal+3];
int dp[maxN][maxN];
void normalize()
{
    for(i=0;i<=maxVal;i++)
        x[i]=-1;
    for(i=0;i<n;i++)
        nxt[i]=x[v[i]],
        x[v[i]]=i;
    int a=0;
    for(i=0;i<=maxVal;i++)
        for(int poz=x[i];poz!=-1;poz=nxt[poz])
            v[poz]=a++;
}
int main()
{
    freopen("s2c.in","r",stdin);
    freopen("s2c.out","w",stdout);
    scanf("%d",&T);
    while(T--)
    {
        sol=1;
        scanf("%d",&n);
        for(i=0;i<n;i++)
            scanf("%d",&v[i]);
        normalize();
        for(i=0;i<n;i++)
            dp[0][i]=1;
        for(i=1;i<n;i++)
        {
            for(j=0;j<n;j++)
                dp[i][j]=1;
            for(j=0;j<i;j++)
                dp[i][v[j]]=1+dp[j][v[i]];
            for(j=1;j<n;j++)
                dp[i][j]=max(dp[i][j],dp[i][j-1]);
            sol=max(sol,dp[i][n-1]);
        }
        printf("%d\n",sol);
    }
    return 0;
}