POJ 1631-Bridging signals 最长上升子序列

//Bridging signals 1631 最长上升子序列 dp问题 2010.8.13
#include<iostream>
using namespace std;
const int MAXP=40005;
int L[MAXP];
int bSearch(int left,int right,int num)
{
    if(right==left)

        return left;

    int mid=(left+right)/2;

    if(num==L[mid])

        return mid;

    else    if(num>L[mid])

    {

        if(right<mid+1)

            return mid;

        else 

            return bSearch(mid+1,right,num);

    }

    else if(num<L[mid])     {         if(left>mid-1)

            return mid;

        else

            return bSearch(left,mid,num);

    }

    else return mid;

}

int solve(int n)

{

    int ans=0;

    int temp=0;

    int count=0;

    scanf("%d",&temp);

    L[ans++]=temp;

    n--;

    while(n--)

    {

        scanf("%d",&temp);

        if(temp>L[ans-1])

            L[ans++]=temp;

        else

            L[bSearch(0,ans-1,temp)]=temp;

    }

    return ans;

}

int main()

{

    int t,n;

    cin>>t;

    while(t--)

    {

        cin>>n;

        cout<<solve(n)<<endl;
    }
    return 0;
}