LIS

一句话理解

LIS 最长上升子序列。

为什么要学

经典线性 DP。

讲解

f[i] 以 i 结尾的 LIS。转移 max{f[j]+1 | j<i, a[j]<a[i]}。O(n²)。还有 n log n。

例子

子序列可不相邻，和子数组不同。

常见错误

• 当成连续。
• 严格上升和可相等没看题。