算法导论15.4-6：最长单调递增子序列
发布时间
阅读量：
阅读量
参考文献：
《编程之美》一书中第2.16节
http://blog.pfan.cn/rickone/13086.html
http://chriszeng87.iteye.com/blog/1054321
设计一种时间复杂度为O(nlogn)的算法使其能够找到一个包含n个元素的序列中最长递增子序列
O(n²)相对容易理解；未加深入研究；后又研读了O(n log n)的具体解析以及众多大神的研究心得后才有所体会；也感受到其中奥秘无穷
对于序列{S_n}，我们考虑其长度为i的所有单调递增或递减子列（其中1≤i≤m）。选择这些子列中最后一个元素的最小值，并将其记作L_i。则有以下关系式成立：L₁ ≤ L₂ ≤ … ≤ L_m。
序列a1, a2, …, an，从左至右扫描序列（可用二分法），对于每一个ai，它可能
(1) ai<L1，那么L1=ai
(2) ai>=Lm，那么Lm+1=ai，m=m+1 (其中m是当前见到的最大的L下标)
(3) Ls<=ai<Ls+1，那么Ls+1=ai
以上就是binarySrh中完成的主要任务。
数组a:1 3 5 2 3
通过改进后的二分查找方法确定了最长递增子序列的最大长度... 得到maxL数组中的值依次为1、2、3... 其中maxL数组中元素的数量len直接对应于最长递增子序列的长度... 对于这一点我也仅能有所体会而非深入论证
2、如果要得到子序列的内容应该怎么做呢？
可以在遍历过程中，在每一步中通过mem数组记录当前处理过的元素及其对应的最长递增子序列长度j（其中j代表该位置对应的最长递增子序列的长度）。当整个过程结束后，在逆序访问该数组时即可依次获取长度依次递减至1的所有最长递增子序列的结尾元素，并最终确定了完整的最长递增子序列结构。
#include<iostream>
using namespace std;
int binarySrh( int *s, int len, int x ) #二分查找
{
int left = 0,right = len-1, mid = (left+right)/2;
while( left<=right )
{
if( x>s[mid] ) left = mid+1;
else if( x<s[mid] ) right = mid-1;
else return mid;
mid = (left+right)/2;
}
cout << left << ' ';
return left;
}
int main()
{
int n = 10;//原始数组长度
int a[10] = { 6, 1, 8, 3, 10, 11, 12, 13, 4, 5 };
int maxL[10] = { 0 };//maxL[i]记录长度为i子序列的最小尾数
int mem[10] = { 0 };//mem[i]表示以a[i]结尾的最长子序列 maxL[0] = a[0];
int len = 1;//length
for( int i=1; i<n; i++ )
{
int j = binarySrh( maxL, len, a[i] );
maxL[j] = a[i];
mem[i] = j;
if( ++j>len )
len = j;
}
cout << "max length: " << len << endl;
cout << "longest subsequence: ";
int currMaxLen = len-1;
for( int i=0; i<n; i++ )
cout << mem[i] << " ";
cout << endl;
for( int i=9; i>=0&&currMaxLen>=0; i-- ) {
if( mem[i]==currMaxLen ) {
cout << a[i] << " "; //反向输出子序列
currMaxLen--;
}
}
cout << endl;
return 0;
}全部评论 (0)
还没有任何评论哟~