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

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

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

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

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