soj2804o(logn)最长上升子序列.cpp

来自「一些ACM题目的解答,主要是soj和poj的」· C++ 代码 · 共 44 行

#include<stdio.h>
#include<string.h>

int t[1000000];

int main(void)
{
    int a,len,n;
    int i,j,low,high,mid;
    while(scanf("%d",&n)!=EOF)
    {
        len=0;
        memset(t,0,sizeof(t));
        for(i=0;i<n;i++)
        {
            scanf("%d",&a);
            if(len==0||a>t[len-1])
            {
                t[len++]=a;
            }
            else
            {
                low=0;high=len-1;mid=(high+low)/2;
                while(low<high)
                {
                    if(a>t[mid])
                    {
                        low=mid+1;
                    }
                    else
                    {
                        high=mid;
                    }
                    mid=(high+low)/2;
                }
                t[mid]=a;
            }
        }
        printf("%d\n",len);
    }
    return 0;
}