最长上升子序列(LIS) 和 最长下降子序列(LDS) 分别表示最长上升子序列和最长下降子序列

昨天打算解决一道关于最长上升子序列的问题时,突然回想起过去曾撰写的一篇相关的文章.拿出来重新审视了一下,只觉得心里满篇都是水.
这篇可以说是对上一篇文章内容的一个补充和完善.

最长上升子序列 -----最长不下降子序列
最长不上升子序列 ---- 最长下降子序列

最长上升子序列 和 最长不下降子序列

最长上升子序列的核心思想就是 追加 和 替换

为了实现找到a中的最长递增序列的目标。
为了实现找到a中的最长递增序列的目标, 我们需要建立一个辅助数组lis。
接下来要对a中的每个元素进行评估, 确保能够准确捕捉到递增的趋势。

如果数组 a[] 中的元素 a[i] 大于当前有序序列 lis[] 的末尾元素，则将该元素追加到有序序列末尾；否则，在有序序列中找到第一个 不小于 当前值的位置进行替换操作。
例如：
初始化时取第一个值作为初始序列；
遍历数组中的每一个值进行比较；
对于每一个待比较值：
若当前值大于现有序列末尾，则直接添加到末尾；
否则，在现有序列中找到第一个 不小于 当前值的位置并进行替换。
具体操作过程如下：
初始状态：a[] = \{2,1,3,5,6,4\}；lis[] = \{2\}；
第1步：将a[0]=2加入lis[]；
第2步：处理a[1]=1时发现其小于