最大化给定数组中两个不相交非递减子序列的长度和

寻找数组的最长非递减子序列（LIS）是经典问题，已有时间复杂度为O(n log n)的成熟解法。现在遇到一个变体问题：给定一个至少包含2个元素的数组，找出两个不共享相同索引元素的非递减子序列，目标是最大化并输出二者的长度和。

朴素DP解法的时间复杂度为O(n^4)，存在明显优化空间，我们需要明确以下核心问题：

一、该问题的最优时间复杂度算法是什么？ #

最优解法可以达到O(n log n)的时间复杂度，核心思路是对经典LIS的贪心+二分思想进行扩展：

• 维护两个贪心候选数组：lis1 记录第一个子序列的最优候选元素，lis2 记录第二个子序列的最优候选元素
• 遍历数组时，对每个元素判断它能加入lis1、lis2的哪个位置，或者替换其中的元素以保证后续能容纳更长的子序列，同时跟踪两个子序列的长度和的最大值

另一种等价思路是将问题转化为求数组的二维LIS，每个元素对应一个二维状态（代表它在两个子序列中的角色），最终通过二分优化实现线性对数级的时间复杂度。实际工程中，基于LIS扩展的O(n log n)解法是最常用的实现方式。

二、贪心思路的正确性与近似性分析 #

贪心思路：先找出数组的最长非递减子序列并移除这些元素，再在剩余数组中查找最长非递减子序列，时间复杂度为O(n log n)。

1. 该贪心解法不正确，反例如下 #

考虑数组：[3, 1, 4, 1, 5, 9, 2, 6]

• 第一步找到的LIS是[1, 4, 5, 9]（长度4），移除后剩余数组为[3, 1, 2, 6]
• 剩余数组的LIS是[1, 2, 6]（长度3），二者长度和为7

但最优解是选择两个子序列：[3, 4, 5, 9]（长度4）和[1, 1, 2, 6]（长度4），长度和为8，明显大于贪心得到的结果。这说明贪心策略会因为第一次选取的LIS占用了关键元素，导致第二个子序列无法达到最大可能长度，因此无法得到最优解。

2. 贪心解法的近似性能保证 #

虽然贪心解法无法得到最优解，但它是一个有常数性能保证的近似算法：

假设最优解的两个子序列长度分别为a和b，最优和为S = a + b。原数组的LIS长度至少为max(a, b)，因此贪心第一步得到的长度≥max(a, b)；而S = a + b ≤ 2*max(a, b)，所以贪心得到的和G ≥ max(a, b) ≥ S/2。也就是说，贪心解法得到的结果不会小于最优解的一半，是一个2-近似算法。

内容的提问来源于stack exchange，提问作者tsh