改了,还是错的
#include<stdio.h>
long a[1001],d[1001];
main()
{long i,n,len=0;
 long mid,left,right;
 scanf("%ld",&n);
 for(i=0;i<n;i++)
  {scanf("%ld",&a[i]);
   d[i]=0;
  }
 for(i=0;i<n;i++)
  {
   if(a[i]>d[len])
     d[++len]=a[i];
   else
   {
	 left=1;
	 right=len;
	  while(left<=right)
	 {
	  mid=(left+right)/2;
	  if(d[mid-1]<a[i]&&d[mid]>=a[i])break;
	  if(a[i]>d[mid])
	    left=mid+1;
	  if(a[i]<d[mid])
	    right=mid-1;
	 }
	 if(left<=right)d[mid]=a[i];
   }
  }
  printf("%ld",len);
 return 0;
}

• n^2的我早过拉,假如是50000,铁定超时.所以我想写个N*LOGN的,二分老写不对 (0) yiyiyi4321 2005-12-16 13:54:59
• 嗯，到你们那试了下，50001规模的 187ms AC了。 哪里还可优化呢？ (5) wrong123 2005-12-16 23:16:27