出自蓝书《算法竞赛入门经典训练指南》
求最长上升子序列是很常见的可以用动态规划解决的问题……
很容易根据最优子结构之类的东西得出
$\text{dp}[i]$为以第i个数结尾的最长上升子序列长度
定义$\max{\emptyset}=0$，粗略地写出
\[\text{dp}[i] = \max \left\{ \text{dp}[j]|0\leqslant j < i,A[j] < A[i] \right\} + 1\]
状态数$\mathcal{O}({n})$，如果直接枚举转移，转移数$\mathcal{O}({n})$，时间复杂度$\mathcal{O}({n^2})$
现在想办法加速转移……
设$\text{dp}^{-1}[x]$为$x=\text{dp}[i]$中$\text{A}[i]$最小的$i$
设$\text{pd}[x]=\text{A}[\text{dp}^{-1}[x]]$
若有$\text{A}[i]<\text{A}[j]$且$\text{dp}[i]==\text{dp}[j]$，那么之后的元素只需要比$\text{A}[i]=\text{pd}[x]=\text{pd}[\text{dp}[i]]$大就可以用$\text{dp}[i]$进行转移
很容易得\[\text{pd}[1]\leqslant \text{pd}[2]\leqslant \text{pd}[3]\leqslant \cdots \leqslant \text{pd}[n] \tag{1}\label{1} \]
\[\text{dp}[i]=\max\left\{x|0\leqslant j < i,\text{pd}[x]<A[i]\right\}+1\]
即最大的小于A[i]的下标加1，也就等价于最小的大于等于A[i]的下标，设为$k$ $\tag{2}\label{2}$
因为最后$[l,r)$区间收缩到$\emptyset$时左侧区间最后一个元素加一就是右侧区间第一个元素
用STL的lower_bound就不需要自己写二分了
因为$\eqref{1}\eqref{2}$，所以$A[i]\leqslant \text{pd}[k]$，转移以后需要更新$\text{pd}[k]$
但是之前少考虑了$0\leqslant j < i$，只需将未计算的$\text{pd}[x]$设为INF就好了= =
时间复杂度$\mathcal{O}(n\log n)$
代码
REPE(i,1,n) pd[i]=INF; REP(i,0,n) { int k=lower_bound(pd+1,pd+1+n,A[i])-g; dp[i]=k; pd[k]=A[i]; }
很容易得最长非降子序列只需将lower_bound改为upper_bound（同样照着二分的参考图）
然后最长下降子序列只需添加greater<int>()参数，并且初始化为-INF
注意dp为以第i个数结尾的长度，所以求最长还需求一遍max
转载于:https://www.cnblogs.com/sahdsg/p/10622662.html
