Poj Solution 1631

http://poj.org/problem?id=1631

#include <stdio.h>
#include <algorithm>

using namespace std;

int a[40000], n;
int ans[40000];
int id[40000], m;

bool cmp( int s1,int s2 )
{
    return a[s1] < a[s2];
}

int main()
{
    int i, j, s;
    int cas;

    scanf( "%d", &cas );
    while( cas-- )
    {
        scanf( "%d", &n );
        for( i=0; i<n; i++ )
            scanf( "%d", &a[i] );

        ans[0] = 1; id[0] = 0;
        for( i=1, m=1; i<n; i++ )
        {
            if( a[ id[m-1] ] < a[i] )
            {
                id[m] = i;
                ans[i] = ans[ id[m-1] ] + 1;
                m++;
            }
            else
            {
                j = lower_bound( id, id+m, i, cmp ) - id;
                ans[i] = ans[ id[j] ];
                id[j] = i;
            }
        }

        printf( "%dn", ans[ id[m-1] ] );
    }

    return 0;
}