[ACM] Longest increasing subsequence

#include <cstdio>
int main() {
    int a[1000],maxlen[1000]={0};
    int *p,*max=maxlen;
    int i,j,N;
    scanf("%d",&N);
    for(i=0;i<N;i++) {
        scanf("%d",a+i);
        p=maxlen+i;
        for(j=0;j<i;j++)
            if(a[j]<a[i]&&maxlen[j]>*p)
                p=maxlen+j;                 //求以a[i]为终点的最长上升子序列长度
        maxlen[i]=*p+1;
        if(maxlen[i]>*max)
            max=maxlen+i;
    }
    printf("%d\n",*max);
    return 0;
}

Leave a Reply

Your email address will not be published. Required fields are marked *