带索引约束的最长递增子序列（LIS）高效求解问询

当然有更优的解法！我们可以把整体时间复杂度降到 O(N log N)，比朴素的O(N² log N)高效得多。核心思路是拆分问题，分别计算两个辅助数组，再合并结果。

核心思路 #

对于每个索引i（1-based），必须包含arr[i]的最长递增子序列（LIS）长度，可以拆分为两部分：

• 从数组开头到i的位置，以arr[i]结尾的最长严格递增子序列长度（记为left[i]）——这部分代表arr[i]左边能衔接的最长递增序列。
• 从i的位置到数组结尾，以arr[i]开头的最长严格递增子序列长度（记为right[i]）——这部分代表arr[i]右边能衔接的最长递增序列。

最终，必须包含arr[i]的LIS长度就是 left[i] + right[i] - 1（减去重复计算的arr[i]本身）。

步骤详解 #

1. 计算left数组（O(N log N)） #

left[i]表示以arr[i]结尾的最长严格递增子序列长度，用经典的LIS优化算法计算：

• 维护一个tails数组，tails[k]代表长度为k+1的严格递增子序列的最小末尾元素。
• 遍历数组从左到右：
  • 对于当前元素num = arr[i]，用二分查找找到tails中第一个大于等于num的元素位置（严格递增的情况）。
  • 如果num比tails最后一个元素大，直接追加到tails末尾，此时left[i] = len(tails)。
  • 否则，替换tails中找到的位置的元素，此时left[i] = 找到的位置 + 1（因为数组索引从0开始，长度是索引+1）。

2. 计算right数组（O(N log N)） #

right[i]表示以arr[i]开头的最长严格递增子序列长度，我们可以用类似的逻辑，只是从右到左遍历，调整二分查找的条件：

• 维护一个tails数组，tails[k]代表长度为k+1的严格递增子序列的最小开头元素（从右往左看）。
• 遍历数组从右到左：
  • 对于当前元素num = arr[i]，用二分查找找到tails中第一个大于等于num的元素位置。
  • 如果num比tails最后一个元素小（因为从右往左看，我们要找比num大的元素形成递增序列），直接追加到tails末尾，此时right[i] = len(tails)。
  • 否则，替换tails中找到的位置的元素，此时right[i] = 找到的位置 + 1。

小技巧：如果觉得从右到左的逻辑容易混淆，也可以把数组反转，将每个元素取反，然后用计算left数组的方法得到结果，再反转回来就是right数组——取反后，原数组的严格递增序列会变成严格递减，反转后就可以用常规的LIS算法处理。

3. 计算最终结果（O(N)） #

遍历每个索引i，计算left[i] + right[i] - 1，就是必须包含arr[i]的LIS长度。

示例验证 #

示例1：数组[1,2]（严格递增） #

• left数组：[1, 2]
  • 第一个元素1：tails = [1]，left[0] = 1
  • 第二个元素2：比1大，追加到tails，tails = [1,2]，left[1] = 2
• right数组：[2, 1]
  • 第二个元素2：right[1] = 1
  • 第一个元素1：右边的2比1大，所以right[0] = right[1] + 1 = 2
• 最终结果：
  • i=1（对应数组索引0）：1 + 2 - 1 = 2，符合示例。

示例2：数组[2,2]（严格递增） #

• left数组：[1, 1]
  • 第一个元素2：tails = [2]，left[0] =1
  • 第二个元素2：找到tails中第一个大于等于2的位置0，替换，left[1] = 1
• right数组：[1,1]
  • 第二个元素2：right[1] =1
  • 第一个元素2：右边的2不大于它，所以right[0] =1
• 最终结果：
  • i=1（对应数组索引0）：1+1-1=1，符合示例。

非严格递增的调整 #

如果题目要求的是非严格递增子序列（即允许元素相等），只需要把二分查找的条件从大于等于改成大于即可，这样相等的元素可以被纳入子序列。

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