algorithm - 约束最长递增子序列

Question

考虑一个包含N整数的数组。现在我们得到了一个 index i，它可以从1through中获取值N。此特定索引应始终存在于我们生成的 LIS 中。计算 处的每个值的 LIS i。

我们如何才能有效地解决上述问题？我直接的解决方案是改变i所有值的索引并计算 LIS。时间复杂度上升到 O(N ² log(N))。能打吗？

例子：

N = 2。我 = 1

假设给定的数组是 [1,2]。

[1,2]或者[2, 2]

在每种情况下，最长（严格）递增的子序列是2和1。

Answer 1

LIS 的规范动态程序为每个 计算k索引处元素的最长递增子序列，1..k其中包括索引处的元素k。使用该数据和最长递增子序列的镜像数据k..n，我们找到包含索引的LISk作为最长之前k和最长之后的并集k。

O(n log n)

Answer 2

拥有一个必须在子序列中的索引 i 可以轻松地向左和向右看，看看你可以走多远才能保持严格递增。这最多需要 O(N) 步。

直接的解决方案现在只需对索引 i 处的所有 N 个值重复此操作，总工作量为 O(N^2)。

但请注意，当更改索引 i 处的值时，可以重复使用之前完成的计算。只需要检查序列是否可以在任一方向上延伸到 i 之外，如果是，您已经知道多远（或者现在可以一劳永逸地计算它）。

这将总工作量降低到 O(N)。