最长上升子序列LIS

$\Theta(n^2)$

$f_i=max(f_j+1),j<i,a_j<a_i$

$\Theta(nlogn)$

限制条件二维偏序，bit优化

 

最长公共子序列LCS

$\Theta(n^2)$

$f_{i,j}=max(f_{i-1,j},f_{i,j-1},[a_i==b_j]f_{i-1,j-1}+1)$

$\Theta(nlogn)$

可以转化为LIS：

无重复值：把b中的值替换为a中该值出现的位置，在b上做LIS的算法二

有重复值：把b中该值替换为a中该值出现的位置集合（降序保证每个集合只选一个），同上LIS，注意替换后序列可能很长，上限n^2。可能卡爆空间

 

最长公共上升子序列LCIS

$\Theta(nm^2)$

设$f_{i,j}$为考虑了A串的前i位，LIS的结尾在j的LCIS。注意：i为阶段

$f_{i,j}=f_{i-1,j},a_i\neq b_j \\
f_{i,j}=max(f_{i,k}+1),a_i=b_j,b_k<b_j$

$\Theta(nm)$

j在从1扫到m时，维护$<a_i$的最优决策点。详见LYD。