最长上升子序列（LIS） nlogn方法

a[]数组存原序列

ans[] 第i位 表示 长度为 i 的 上升子序列的结尾 最小为 ans[i]

a[]={4,2,6,3,1,5} len为最长上升子序列长度

模拟过程：

先 ans[1]=a[1]. ans={4} len=1

a[2]=2, 2 小于 ans[len] ，即 2 < 4 , 所以 2可以替换4。 ans={2}， len=1

a[3]=6, 6 大于 ans[len] , 即 6 > 2， 所以6可以加入上升序列 ans[++len]=6, ans={2,6}, len=2

a[4]=3, 3<6并且 3>2，显然，应该用3替换2 所以 ans[len]=3， ans={2,3} len=2

a[5]=1, 1<2 所以 1 替换 2， ans[1]=1, ans={1,3} len=2

a[6]=5, 5>3 所以 5 加入序列 ans[++len]=5, ans={1,3,5}, len=3

最长上升子序列长度为3

算法流程：

定义 原数组 a， 答案数组 b
枚举 a 数组中的每个元素
如果大于b的最后一个元素
当前元素加入 b
答案长度+1
否则
二分查找 a当前元素 替换 b 中的位置
替换 b 中 的 元素


题目链接

题意：求给出序列的最长上升子序列

#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
vector<int> a, ans;
vector<int>::iterator t; 
int main(){int n, T;scanf("%d", &T );while( T-- ){a.clear(); ans.clear();scanf("%d", &n );for ( int i=1, x=0; i<=n; i++ ) scanf("%d", &x ), a.push_back(x);ans.push_back(a[0]);for ( int i=1; i<a.size(); i++ ){if( a[i]>ans[ans.size()-1] ) ans.push_back(a[i]);else {t=lower_bound(ans.begin(), ans.end(),a[i]);*t=a[i];}}printf("%d\n", ans.size() );}
}