[内容有误] 最长不下降子序列描述有误

[hhc0001]

请选择：

• 我正在着手修复这个问题

我正在访问这个页面

动态规划基础

我发现页面有这样的问题

首先，定义 $a_1 \dots a_n$ 为原始序列，$d$ 为当前的不下降子序列， $len$ 为子序列的长度，那么 $d_{len}$ 就是长度为 len 的不下降子序列末尾元素。

初始化：$d_1=a_1,len=1$。

应修改为

首先，定义 $a_1 \dots a_n$ 为原始序列，$d_i$ 为长度为 $i$ 的所有的上升子序列的末尾的数的最小值， $len$ 为当前搞出的最长不下降子序列的长度，那么 $d_{len}$ 就是长度为 $len$ 的不下降子序列末尾元素。

Reference

OI-wiki 中最长不下降子序列的参考资料的原文

[hhc0001]

事实上在测了 一本通求最长不下降子序列的题目 的样例之后都没过，如图：

可以看到，这个算法输出的东西，连子序列都不是。

[LeoJacob]

同意 $O(n \log n)$ 算法的描述有问题。

除了准确性以外，该算法的表述类似“跟着我做 1 2 3 就做出来了”，对于初学者不友好。建议修改时按以下步骤展示：

1. 描述 $d$ 数组的准确定义；
2. 描述如何利用 $d$ 数组完成原有问题；
3. 描述 $d$ 的单调性；
4. 描述如何利用 $d$ 的单调性采用二分优化；
5. 给出代码。

[hhc0001]

接受，正在修改