algorithm - 子序列是否需要连续

Question

我是动态规划的新手，正在阅读最长递增子序列 (LIS) 问题。

解决方案表明序列不需要像原始数组那样连续。中间可以跳过元素；但我有另一种印象。

能否请您帮助澄清这个困惑。

举个例子:a = {10,22,9,33,55,66,12,90}LIS 是 {10,22,33,55,66,90} => 6

不过，我认为它会是 {33,55,66}

谢谢

Answer 1

子序列不需要是连续的。子序列是通过从数组中删除零个或多个元素而形成的。另一方面，子数组总是连续的。让我们举个例子:

a = {10,22,9,33,55,66,12,90}

这里，{10,22,33,55,66,90}是最长递增子序列，{33,55,66}是最长递增子数组.

所以，您基本上要回答的是最长递增子数组问题的解决方案。