题目信息:http://acm.nyist.net/JudgeOnline/problem.php?pid=214
方法一。时间复杂度为O(n*n)
经典动态规划,利用一个数组f[i]表示从a[i]开始的最大递增子序列的长度,
然后max=max(f[i]) { i=1,2,3..n},在OJ上超时了,上网查了下,下面为大牛们的优化算法
。
方法二。时间复杂度为O(n*logn)
由第一种算法知,给个例子,a[6]={8,9,4,5,6,3},在元素6之前,max最大递增子序列为2,一种是8,9 一种4,5,而后一种的最大元素为5,。。
此时可以采取一个一维数组存取f[i](最大递增子序列长度为i)元素的最大值.在利用二分查找,因为f[i]的最大值已经排序了,有D1<D2<D3..
AC code
#include<iostream> using namespace std; int f[100001],a[100001]; int binarysearch(int x,int len) { int left=1,mid,right; right=len; mid=(left+right)/2; while(left<=right) { if(x>f[mid]) left=mid+1; else if(x<f[mid]) right=mid-1; else return left; mid=(left+right)/2; } return left; } int main() { int t,n,j,len; while(cin>>n,!cin.eof()) { len=1; for(int i=0;i<n;++i) cin>>a[i]; f[1]=a[0]; // for(int k=1;k<n;++k) { j=binarysearch(a[k],len); f[j]=a[k]; if(j>len) len=j; } cout<<len<<endl; } // system("pause"); return 0; }