首页 > 代码库 > 最大上升子序列算法
最大上升子序列算法
寻找a[1]..a[n]的最大上升子序列时,可以用的dp[]来记录最大的子序列长度,有状态转移方程:
dp[i] = max{dp[j]}+1, 1<=j<i,a[j]<a[i]
这个算法的时间复杂度O(n^2),代码如下:
int LTS(int *a,int *dp,int len){ int max=0; for(int i=0;i<=len;i++){ dp[i]=1; for(int j=0;j<i;j++) if(a[j]<a[i]) dp[i]=dp[i]>(dp[j]+1)?dp[i]:(dp[j]+1); max=max>dp[i]?max:dp[i]; rerutn max; }
现在重点看下算法复杂度为O(nlogn)算法。
现在我们用一个数组d[],使得d[len]=a[k],数组下标用来表示上升子序列的长度,数组值代表序列a[k]的值(可知dp[k]=len)。
假设有d[k]=a[i],则当再读入a[t],当a[t]>a[i]时,d[k+1]=a[t];
但是一般情况下a[t]会大于很多个数,比如说d[k-s]=a[j](a[j]<a[j]),如果我们选取了a[j]进行比较最长上升子序列就少了s个!!那么该跟哪个数进行比较呢?我们可以按照以下步骤。
初始化使d[1]=a[1],当读入a[t]时,对比a[t]与d[max] ( d[max]=a[k],max表示目前的最大上升子序列的长度 ):
1)a[t]>a[k] 则d[max+1]=a[t];
2)否则,在d中利用二分查找找到比a[t]小的最大数d[i],使d[i+1]=a[t]。
第二步是很为关键的。现在我们可以看一个实例就知道为什么这么做。
求数列 1,5,2,3 的最大上升子序列。用这个算法执行过程如下:
d[1]=1;
a[2]>d[1],故d[2]=a[2]=5;
a[3]<d[2],在d中二分查找找到第一个比a[3]小的d[1],故d[1+1]=a[3]=2,d[2]=2;
a[4]>d[2],故d[2+1]=a[4]=3;
可以得到最大上升子序列为3!
原本的d[2]为5后来更新为2,如果不进行更新那么当读入a[4]=3时,就漏掉了一个!这其实是个策略:如果数列中a[x]和a[y],
1)x<y
2)a[x]>a[y]
3)dp[x]=dp[y],
当再读入a[t]要选择时,到底取哪一个构成最优的呢?
显然是选择a[y],因为后面读入的a[t],如果a[x]>a[t]>a[y],那么选择a[x]就会漏掉,而选择a[y]就可以防止漏掉。也就是说我们对于当前读入的数列,都要使:
d[len]=min{ a[i] | dp[i]= len }
在d中利用二分查找找到比a[t]小的最大数d[i],代码如下:
//二叉搜索int SearchBin(int a[],int key,int len){ int low=1,high=len; while(low<=high){ int mid=(low+high)/2; if(a[mid]<key&&a[mid+1]>key) return mid; else if(a[mid]<key) low=mid+1; else high=mid-1; } return 0;}int LTS(int *a,int *d,int len){ d[1]=a[1]; int max_len=1; for(int i=2;i<=len;i++){ if(a[i]>d[max_len]){ d[++max_len]=a[i]; } else{ int t=SearchBin(d,a[i],max_len); d[t+1]=a[i]; } } return max_len;}
最大上升子序列算法