给定数组的两个非递减子序列的最大长度之和

Question

这是一个著名的问题，询问如何从给定数组中找到最长的非递减子序列。这个问题经过充分研究，有 O(n log n) 时间复杂度的解决方案。

我遇到了一个稍微不同的问题：给定一个至少有 2 个元素的数组。从中找到两个非减子序列。这两个子序列不应共享相同的数组元素（索引相同，值不同）。我想最大化并输出长度之和。

一个简单的 DP 解决方案可以在 O(n^4) 内完成。也许可以进行一些优化以使其工作得更好，但我不知道。所以第一个问题是：

• 我们可以用什么算法以最佳时间复杂度来解决这个问题。

另一个简单的想法是找到最长的非递减子序列并将其从原始数组中删除，然后再次重复查找。这可以在 O(n log n) 内完成。但我不知道：

• 贪心解法正确吗？如果是这样，如何证明或论证。如果不是，如何找出反例。
• 如果不是，它可以作为一种有效的近似算法并具有一定的性能保证吗？

Answer 1

正如您自己提到的：

另一个简单的想法是找到最长的非递减子序列并将其从原始数组中删除，然后再次重复查找。这可以在 O(n log n) 内完成。

但是您无法删除它，因为第二个子序列必须位于您已找到的序列的左侧或右侧。 （如果删除第一个序列，您可能会发现一个序列从第一个序列的左侧开始并在其右侧结束（这是不允许的））

算法：

1. 找到最长的非减子序列
2. 找到找到的拳头左侧最长的非递减子序列
3. 找到找到的拳头右侧最长的非递减子序列
4. 取 2 和 3 中找到的第一个和较长的一个。

为什么不能有更好的解决方案？

对我来说这是显而易见的，但你可以尝试像这样开始正式证明：

假设存在序列 a...b 和 c...d 的更好解决方案。
a..b 和 a..c 不能比 1 中找到的序列更长。 ...