最长递归子序列

设L=<a1,a2,…,an>是n个不同的实数的序列，L的递增子序列是这样一个子序列Lin=<aK1,ak2,…,akm>，其中k1<k2<…<km且aK1<ak2<…<akm。求最大的m值。


1.时间复杂度为O(n2)，空间复杂度O(n)的算法


//O(n2)intLIS1(constintarr[],constintsize){vector<int>h;h.push_back(1);intindex=1;intmax=1;while(index<size){intlongest_sub_size=0;for(intj=0;j<index;++j){if(arr[j]<arr[index]&&longest_sub_size<h[j]){longest_sub_size=h[j];if(max<longest_sub_size+1){max=longest_sub_size+1;}}}h.push_back(longest_sub_size+1);++index;}returnmax;}


2.时间复杂度O(n*log n)，空间复杂度O(n)的算法

intBinSearch(intkey,int*d,intlow,inthigh){while(low<=high){intmid=(low+high)>>1;if(key>d[mid]&&key<=d[mid+1])returnmid;elseif(key>d[mid])low=mid+1;elsehigh=mid-1;}return0;}intLIS(int*a,intn,int*d){inti,j;d[1]=a[1];intlen=1;//递增子序列长度for(i=2;i<=n;i++){if(d[len]<a[i])j=++len;elsej=BinSearch(a[i],d,1,len)+1;d[j]=a[i];}returnlen;}