Cod sursă (job #258018)

#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;
        memset(aib,0,sizeof(aib));
        memset(dp,0,sizeof(dp));
        scanf("%d",&n);
        for(i=1;i<=n;i++)
            scanf("%d",&v[i]);
        normalize();
        for(i=1;i<=n;i++)
            for(j=1;j<i;j++)
            {
                int val=query(j,v[i]);
                dp[i][j]=max(dp[i][j],val+1);
                sol=max(sol,dp[i][j]);
                update(i,v[j],dp[i][j]);
            }
        printf("%d\n",++sol);
    }
    return 0;
}