[ACM] Longest increasing subsequence

1,820 Replies

[c]
#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;
}

[/c]

1,820 thoughts on “[ACM] Longest increasing subsequence”

Leave a Reply

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