LIS 最长上升子序列有关问题 nlgn时间打印其中一个序列
LIS 最长上升子序列问题 nlgn时间打印其中一个序列
什么是最长上升子序列？从字面意思就很好理解，就是从一系列顺序输入中，寻找一个上升子序列，要求这个子序列的长度最长。对O(n^2)的解法（DP）这里不讨论了，主要说一下nlgn的解法。网上查了一下，都是通过维护一个数组来实现该算法，但是只给出了求最长上升子序列的长度的代码，没有返回要求的子序列。这里就将此方法扩展一下，使得算法可以返回一个满足条件的子序列。好吧，其实在维基上就有该算法的详细介绍和伪码实现（Longest increasing subsequence），我只是代码搬运工，哈哈哈。下面是算法的c++实现（这里给出的是严格最长上升子序列的代码），如有错误，还望不吝赐教。
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
int main(void){
vector<int> array;
#ifndef ONLINE_JUDGE
freopen("d://file.in", "r", stdin);
#endif
int n;
/*输入序列*/
while(cin >> n)
array.push_back(n);
if(array.size() == 0) return 0;
/*
for(auto a : array) cout << " " << a;
cout << endl;
*/
/*
**这两个数组是这个算法实现的关键
**数组f表示对应长度的上升子序列的最小末尾值在array中的下标，比如f[k]表示长度为k+1的上升子序列的最小末尾值在array的下标为f[k]
**数组pre记录了更改数组f时，f的前一个值，比如pre[j]表示当使用array[j]更新数组f时，pre[j]等于要更新的数组f的位置的前一个的值
*/
vector<int> f(array.size(), 0), pre(array.size(), 0);
int top = -1, maxV = 0;
for(int i = 0; i < array.size(); i++){
/*保存数组f中被更新的地址下标*/
int pos;
/*处理array的第一个数或者array[i]的值大于数组f的所有值，需要增加数组范围，末尾位置上保存下标*/
if(i == 0 || array[i] > array[f[top]]){
f[++top] = i;
pos = top;
maxV = max(maxV, top+1);/*更新最长上升子序列的长度*/
//cout << i << ": " << top << " " << f[top] << endl;
}
else{
/*二分查找数组中大于等于某一个指定值的最小位置*/
int L = -1, R = top, mid;
while(R-L > 1){
mid = (L+R)/2;
if(array[f[mid]] >= array[i]) R = mid;
else L = mid;
}
f[R] = i;
pos = R;
}
/*更新数组pre*/
if(pos == 0) pre[i] = -1;
else pre[i] = f[pos-1];
/*
for(int j = 0; j <= top; j++) cout << " " << f[j];
cout << endl;
cout << i << ": " << f[pos] << " " << pre[i] << endl;
*/
}
/*
for(int j = 0; j <= top; j++) cout << " " << f[j];
cout << endl;
for(auto a : pre) cout << " " << a;
cout << endl;
*/
cout << maxV << endl;
/*根据数组pre重构出最长上升子序列*/
int index = f[top];
vector<int> res;
for(int i = top; i >= 0; i--){
res.insert(res.begin(), array[index]);
index = pre[index];
}
for(auto a : res) cout << " " << a;
cout << endl;
return 0;
}
</span>
上面的算法用到了两个数组：数组f和数组pre
- 数组f表示对应长度的上升子序列的最小末尾值在array中的下标，比如f[k]表示长度为k+1的上升子序列的最小末尾值在array的下标为f[k]。
- 数组pre记录了更改数组时，f的前一个值，比如pre[j]表示当使用array[j]更新数组f时，pre[j]等于要更新的数组f的位置的前一个的值。
当处理到序列的array[i] 时，算法更新数组f中的值，是查找数组中的下标k对应的array[k]大于等于array[i]的在数组f中的最小位置。真的好拗口，其实就是说为了找最长上升子序列，我们要子序列的前面部分尽可能的小，也就是所谓的对应长度的上升子序列的最小末尾值。至于数组pre是保存了数组f的更新状态，其实在更新数组f时一定已经出现了满足要求的数组，但是可能因为后面的输入又把某些值更改了。好费劲，来个实例吧。
例如：1 3 4 9 15 2 3 9
第0次：处理array[0]
数组下标：0
1 2
3 4 5
6 7
数组f：0
数组pre：-1
第1次：处理array[1]
数组下标：0
1 2
3 4 5
6 7
数组f：0
1
数组pre：-1
0
第2次：处理array[2]
数组下标：0
1 2
3 4 5
6 7
数组f：0
1 2
数组pre：-1
0 1
第3次：处理array[3]
数组下标：0
1 2
3 4 5
6 7
数组f：0
1 2
3
数组pre：-1
0 1
2
第4次：处理array[4]
数组下标：0
1 2
3 4 5
6 7
数组f：0
1 2
3 4
数组pre：-1
0 1
2 3
第5次：处理array[5]
数组下标：0
1 2
3 4 5
6 7
数组f：0
5 2
3 4
数组pre：-1
0 1
2 3 0
第6次：处理array[6]
数组下标：0
1 2
3 4 5
6 7
数组f：0
5 6
3 4
数组pre：-1
0 1
2 3 0
5
第7次：处理array[7]
数组下标：0
1 2
3 4 5
6 7
数组f：0
5 6
7 4
数组pre：-1
0 1
2 3 0
5 6
数组f的最后位置的内容为最长子序列值的末尾值的在array中的下标，以此为起点来重构出子序列。
给出其他几个测例：
1 2 3 4 7 7 7 8 8 8 ：
maxV：6
子序列：1 2 3 4 7 8
f：0 1 2 3 6 9
pre：-1 0 1 2 3 3 3 6 6 6
1 1 1 1 1 1 1 1 1 1：
maxV：1
子序列：1
f：9
pre：-1 -1 -1 -1 -1 -1 -1 -1 -1
maxV：5
子序列：1 2 3 9 14
f：0 5 6 7 8
pre：-1 0 1 2 3 0 5 6 7
maxV：5
子序列：1 2 3 9 15
f：0 5 6 7 8
pre：-1 0 1 2 3 0 5 6 7