什么是最长上升子序列？从字面意思就很好理解，就是从一系列顺序输入中，寻找一个上升子序列，要求这个子序列的长度最长。对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_JUDGEfreopen("d://file.in", "r", stdin);#endifint 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]
数组下标：01234567
数组f：0
数组pre：-1
第1次：处理array[1]
数组下标：01234567
数组f：01
数组pre：-10
第2次：处理array[2]
数组下标：01234567
数组f：012
数组pre：-101
第3次：处理array[3]
数组下标：01234567
数组f：0123
数组pre：-1012
第4次：处理array[4]
数组下标：01234567
数组f：01234
数组pre：-10123
第5次：处理array[5]
数组下标：01234567
数组f：05234
数组pre：-101230
第6次：处理array[6]
数组下标：01234567
数组f：05634
数组pre：-1012305
第7次：处理array[7]
数组下标：01234567
数组f：054
数组pre：-10123056
数组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
1 3 4 9 15 2 3 9 14：
maxV：5
子序列：1 2 3 9 14
f：0 5 6 7 8
pre：-1 0 1 2 3 0 5 6 7
1 3 4 9 15 2 3 9 15：
maxV：5
子序列：1 2 3 9 15
f：0 5 6 7 8
pre：-1 0 1 2 3 0 5 6 7
累死累活不说，走马观花反而少了真实体验，
