引入
以下记 \(s\) 的长度为 \(n\)，\(t\) 的长度为 \(m\)。
一些问题：
-
什么是子序列？
称 \(t\) 是 \(s\) 的子序列，即是 \(s\) 删掉一些元素（可以什么都不删）后可以得到 \(t\)。
-
什么是上升子序列？
称 \(t\) 是上升子序列，仅当 \(s\) 的子序列 \(t\) 满足 \(\forall i\in[1,m),t_i<t_{i+1}\)（即单调上升）。
-
什么时最长上升子序列？
是上升子序列中长度最长（可能多个）的。
（最长不降子序列同理。）
以下将最长上升子序列简写为 LIS。
求法
\(O(n^2)\) 求长度
记 \(dp_i\) 表示 \(s\) 的前缀 \(s[1\dots i]\) 的 LIS 的长度，并制约：\(s[1\dots i]\) 的 LIS 必须以 \(s_i\) 结尾。
可以发现，因为我们一定要选 \(s_i\)，我们可以枚举上一个选的 \(s_j\)，并用 \(dp_j\) 更新 \(dp_i\)：
\[dp_i=\max\{dp_j+1\},1\le j<i\le n \]很好理解，因为一定选 \(s_i\)，所以长度要加 \(1\)。
答案是 \(\max\{dp_i\},1\le i\le n\)，因为每一个 \(1\le i\le n\) 都可能当 LIS 的结尾。
这样做是 \(O(n^2)\) 的。能否优化？
\(O(n\log n)\) 求长度
发现当 \(s[1\dots i-1]\) 的 LIS 中最后一个数小于 \(s_i\) 时，\(s[1\dots i]\) 的 LIS 可以照抄 \(s[1\dots i-1]\) 的，并在最后加上 \(s_i\)。
原因：（为方便，暂时记 \(s[1\dots i-1]\) 的 LIS 为 \(t\)）
\[\overbrace{t_1<t_2<\cdots<t_m}^{\text{LIS 原有条件}}<s_i \]依然单调上升。
我们当然希望每次都满足这个条件，但不满足怎么办？
臆想：直接将 \(s_i\) 替换进 \(t\)。
其实有一定合理性。我们将设法用 \(s_i\) 替换 \(t\) 中某个位置，并让 \(t\) 依然单调递增。这个位置上的数是第一个大于 \(s_i\) 的。它可以二分确定（因为 \(t\) 单调递增）。
但 \(t\) 就没有了顺序性：后来的 \(s_i\) 反而跑到了前面，所以这个操作使 \(t\) 不合法。
其实这个操作并不影响 \(t\) 的长度，所以答案不会变劣。但可能变好：如果 \(s_i\) 刚好是答案序列的一部分，那么它使 \(t\) 的字典序变小，递增长度可能更长，答案可能会变得更大。（其实挺玄学的。）
最后，我们得到了一个 \(O(n\log n)\) 求 LIS 长度的算法。
如果求字典序最小的 LIS 呢？
\(O(n\log n)\) 求字典序最小的 LIS
未完待续……
标签：dots,le,LIS,序列,长度,上升,最长,dp From： https://www.cnblogs.com/chargedcreeper/p/lis.html