LIS问题的优化

普通的LIS问题的时间复杂度是\(O(n^2)\)，瓶颈主要是在方程\(f[i]=1+max(f[j])\)，其中\(1≤j＜i\)且\(a[j]<a[i]\)中寻找\(j\)上

我们尝试用贪心优化，这里的\(j\)就是小于\(i\)的比\(a[i]\)小的且\(f[j]\)最大的\(j\)

根据贪心原则，假设当前循环到了\(i\)（还没有开始处理），我们用\(h[k]\)表示\(f[j]\)为\(k\)且\(a[j]\)最小的\(a[j]\)（\(1≤j＜i\)）

假设当前循环到了\(i\)，此前的最优长度为\(len\)

那么如果\(a[i]>h[len]\)，那么就可以\(len\)++,\(h[len]=a[i]\)

否则的话，我们可以发现\(h\)是单调的（为什么见下），于是我们二分，找到一个位置\(l\)，满足\(l\)是最大的且\(h[l]<a[i]\)，然后就有\(f[i]=l+1\)，再考虑修改，肯定就是\(h[l+1]=min(h[l+1],a[i])\)，此时修改后\(h\)仍然是单调的，所以\(h\)一直都是单调的

当然上述方法有一定思维含量，我们可以利用数据结构来减少思维含量

我们将\(a\)离散化，设\(h[k]\)表示值为\(k\)（离散化后）的最大的\(f\)，我们查找区间\([1,a[i]-1]\)的最大值就好了