最长不下降子序列题解

备注：$A$表示长度为$n$的序列。

普通动态规划

设$f_i$表示以$A_i$为结尾的最长不下降子序列的长度，那么每次枚举$f_i$时，我们都要寻找$A_i$前面接的数字，并使接上这个数字后最长不下降的子序列的长度最大。所以我们要枚举$j$，并且$j$满足$A_j\le A_i,j<i$，$f_i$就等于符合条件且最大的$f_j+1$。
时间复杂度为$O(n^2)$，会超时。

正解动态规划

设$f_i$表示长度为$i$的不下降子序列的最后一个数的最小值，$maxn$表示最长不下降子序列的长度，那么输入$A_i$时有以下情况：

$1.A_i>f_{maxn}$

这时最长不下降子序列的长度将增加$1$，而新的最长不下降子序列的最后一个数的最小值将是$A_i$。

$2.$除上述情况以外

$A_i$有可能是长度为$x$的不下降子序列的最后一个数的最小值，因此用二分查找找到满足 $f_x<A_i,f_{x+1}\ge A_i$的$x$，并将$f_x$替换为$A_i$。如果不这么做，后面输入的$A_{i+1}$有可能小于原来的$f_x$，大于$A_i$，此时不下降子序列的长度可增加$1$，但由于$f_x$未更新，所以程序不会这么做，这时答案会错误。

时间复杂度为$O(n\log n)$。