最长递增子序列(LIS)O(n log n)返回实际序列实现问题与算法讲解求助

1. 现有实现与参考算法问题诊断 #

你当前的代码存在两个核心错误：

• 直接将indexes数组的值作为最终子序列的索引：indexes数组的作用是维护长度为k+1的递增子序列的最小末尾元素下标，本身存储的索引顺序不是最终LIS的实际顺序，必须通过你定义的helper前驱数组回溯才能得到正确序列。你参考的视频算法核心逻辑是正确的，只是你遗漏了最后回溯前驱的步骤，才会导致除演示用例外其他输入结果错误。
• 二分函数选择不符合需求：如果要求严格递增的LIS，应该使用bisect_left而非bisect_right，bisect_right仅适用于求非严格（允许相等元素）的递增子序列场景，这也是你测试[1, 8, 6, 4, 9, 8, 3, 5, 2, 7, 1, 9, 5, 7]输入结果错误的核心原因。

2. 可返回实际序列的LIS O(n log n)解法说明 #

核心原理 #

算法维护两个核心数组：

• tails数组（对应你代码里的indexes）：tails[k]表示长度为k+1的所有递增子序列中，末尾元素值最小的那个元素的下标。维护这个数组的意义是更小的末尾元素能为后续元素提供更大的拼接空间，保证我们能得到最长的子序列。
• prev数组（对应你代码里的helper）：prev[i]表示原数组中下标为i的元素，在它所属的最长递增子序列中的前一个元素的下标，用于最后回溯构建完整序列。

遍历每个元素时的逻辑：

1. 如果当前元素比tails最后一个下标对应的元素大，说明可以拼接成更长的子序列，直接把当前下标加到tails末尾，记录前驱为tails原来的最后一个元素。
2. 否则用二分找到tails里第一个大于等于当前元素的位置（严格递增场景），替换那个位置的下标为当前下标，记录前驱为该位置前一个的tails元素（如果位置>0的话）。
3. 遍历完所有元素后，从tails的最后一个元素开始，顺着prev数组往前回溯，把元素值收集起来再反转，就是正确的LIS。

伪代码 #

输入：整数序列arr，长度为n
初始化：
  tails = 空数组，存储长度为k+1的LIS的最小末尾下标
  prev = 长度为n的数组，全部初始化为-1，存储每个元素的前驱下标
遍历i从0到n-1:
  // 二分查找当前元素应该插入到tails的位置
  left = 0, right = len(tails)
  while left < right:
    mid = (left + right) // 2
    if arr[tails[mid]] < arr[i]:
      left = mid + 1
    else:
      right = mid
  pos = left
  // 替换或新增tails的位置
  if pos == len(tails):
    tails.append(i)
  else:
    tails[pos] = i
  // 记录前驱
  if pos > 0:
    prev[i] = tails[pos - 1]
// 回溯构建LIS
current = tails[-1]
lis = 空数组
while current != -1:
  lis.append(arr[current])
  current = prev[current]
反转lis，得到最终的最长递增子序列
返回lis，长度为len(lis)

可运行Python实现 #

from bisect import bisect_left, bisect_right
from typing import List

def get_lis(sequence: List[int], strict: bool = True) -> List[int]:
    """
    返回最长递增子序列
    :param sequence: 输入整数序列
    :param strict: 是否为严格递增，默认True
    """
    n = len(sequence)
    if n == 0:
        return []
    tails = []
    prev = [-1] * n
    # 根据是否严格递增选择二分函数
    bisect_func = bisect_left if strict else bisect_right
    
    for i in range(n):
        # 提取tails对应的值用于二分查找
        tail_values = [sequence[idx] for idx in tails]
        pos = bisect_func(tail_values, sequence[i])
        # 插入或替换tails对应位置
        if pos == len(tails):
            tails.append(i)
        else:
            tails[pos] = i
        # 记录当前元素的前驱下标
        if pos > 0:
            prev[i] = tails[pos - 1]
    
    # 从末尾回溯前驱构建结果
    current = tails[-1]
    res = []
    while current != -1:
        res.append(sequence[current])
        current = prev[current]
    # 反转得到正序的LIS
    return res[::-1]

# 测试用例
if __name__ == "__main__":
    test1 = [1, 8, 6, 4, 9, 8, 3, 5, 2, 7, 1, 9, 5, 7]
    print(get_lis(test1))  # 输出类似[1, 3, 5, 7, 9]的合法严格递增LIS，长度为5
    test2 = [3, 4, -1, 5, 8, 2, 3, 12, 7, 9, 10]
    print(get_lis(test2))  # 输出类似[-1, 2, 3, 7, 9, 10]的合法LIS，长度为6

注意事项 #

• LIS可能存在多个长度相同的合法解，该算法返回的是其中一个合法解。
• 时间复杂度为O(n log n)，其中n为输入序列长度，每次二分的复杂度为O(log k)，k为当前tails数组的长度，总复杂度符合要求。

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