/* 最长上升子序列 LIS 子段 n^2 子序列 2^n

上升子序列=单调递增 指后面的数大于前面的数

DP-原版 1.状态: f[i] = 以a[i]结尾的LIS; ans = max{f[i]};

2.转移方程 f[i] = max{f[j]+1|a[j]<a[i]}

3.初值 f[i] = 1;

O(n^2)

DP-优化 1.状态: f[i] = 长度为i的LIS的最小结尾; ans = len;

2.转移方程 i 1~n//n if(a[i] > g[len]){ ++len; g[len] = a[i]; } j = lower_bound(f+1,f+1+len,a[i])-f;//log n g[j] = a[i];

3.初值 len = 0 g[0] = 0;

参考代码: 自己写 O(n log n) */