Cod sursă (job #258020)

#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 dp[maxN][maxN],aib[maxN][maxN];
int nxt[maxN],x[maxVal+3];
void normalize()
{
    memset(nxt,0,sizeof(nxt));
    for(i=0;i<=maxVal;i++)
        x[i]=-1;
    for(i=1;i<=n;i++)
        nxt[i]=x[v[i]],
        x[v[i]]=i;
    int a=1;
    for(i=0;i<=maxVal;i++)
        for(int pos=x[i];pos!=-1;pos=nxt[pos])
            v[pos]=a++;
}
void update(int c,int poz,int val)
{
    for(;poz<=n;poz+=lsb(poz))
        aib[c][poz]=max(aib[c][poz],val);
}
int query(int c,int poz)
{
    int res=0;
    for(;poz>0;poz-=lsb(poz))
        res=max(res,aib[c][poz]);
    return res;
}
int main()
{
    freopen("s2c.in","r",stdin);
    freopen("s2c.out","w",stdout);
    scanf("%d",&T);
    while(T--)
    {
        sol=0;
        scanf("%d",&n);
        for(i=1;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;
}