考虑一个数组，它有 N 个整数。现在我们得到了一个索引 i，它可以接受从 1 到 N 的值。这个特定的索引应该始终存在于我们生成的 LIS 中。计算 i 处每个值的 LIS。
我们如何才能有效地解决上述问题呢？我直接的解决方案是改变索引 i 的所有值并计算 LIS。时间复杂度高达 O(N2log(N))。能打吗？
示例:
N = 2.i = 1
假设给定的数组是 [1,2]。
[1,2] 或 [2, 2]
每种情况下最长(严格)递增的子序列是2 和1。
最佳答案
LIS 的规范动态程序为每个 k 计算索引 1..k 处元素的最长递增子序列，其中包括索引处的元素 >k。使用此数据和k..n 的最长递增子序列的镜像数据，我们找到包含索引k 作为 之前最长子序列的并集的LIS k 和 k 之后最长的。
O(n log n)
关于algorithm - 约束最长递增子序列，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/50472478/