如何在线性时间内找出列表中的最长升序子序列？

我想要编写一个能在线性时间内找出列表中最长升序子序列的函数。这看似简单，但不使用嵌套for循环的情况下我却陷入了困境。我的实现思路如下：

if len(L) == 0 or len(L) == 1:
    return len(L)

if all(L[i] == L[0] for i in range(len(L)-1)):
    return len(L)

left = [1] * len(L)
right = [1] * len(L)
count = 1
for i in range(len(L)-1):
    if L[i] <= L[i+1]:
        count += 1
        left[i+1] = count
    else:
        count = 1
        left[i+1] = count

count = 1
for i in range(len(L)-1, -1, -1):
    if L[i] <= L[i-1]:
        count += 1
        right[i-1] = count
    else:
        count = 1
        right[i-1] = count

idx_left = left.index(max(left))
idx_right = right.index(max(right))

if max(max(left), max(right)) == max(left) and idx_left == len(left) - 1:
    return max(left)

你的代码存在的问题 #

1. 数组越界错误：反向遍历循环中，当i=0时，i-1=-1，访问L[i-1]会取到列表最后一个元素，逻辑完全错误，会导致不符合预期的计算结果。
2. 逻辑覆盖不全：left数组仅记录以每个位置结尾的连续升序子序列长度，right数组的遍历方向和判断逻辑混乱，最后仅处理了left数组最大值在末尾的情况，完全覆盖不了所有场景。
3. 冗余判断：判断所有元素相等的逻辑可以被后续遍历自然覆盖，无需单独处理。

针对不同需求的解法 #

情况1：最长连续升序子序列（子数组）

如果你的需求是找连续的升序子序列（即子数组），确实可以做到线性时间，且无需额外数组，用O(1)空间即可实现：

def longest_continuous_increasing_subseq(L):
    if not L:
        return 0
    max_len = current_len = 1
    for i in range(1, len(L)):
        if L[i] >= L[i-1]:
            current_len += 1
            max_len = max(max_len, current_len)
        else:
            current_len = 1
    return max_len

这个方法仅需一次遍历，记录当前连续升序的长度，实时更新最大值即可。

情况2：最长升序子序列（可非连续）

如果是真正的升序子序列（元素可不连续），不存在线性时间的解法，最优时间复杂度为O(n log n)。核心思路是维护一个tails数组，遍历每个元素时用二分查找确定其在tails中的位置并更新数组：

def longest_increasing_subseq(L):
    tails = []
    for num in L:
        left, right = 0, len(tails)
        while left < right:
            mid = (left + right) // 2
            if tails[mid] < num:
                left = mid + 1
            else:
                right = mid
        if left == len(tails):
            tails.append(num)
        else:
            tails[left] = num
    return len(tails)

这个方法通过二分查找将时间复杂度控制在O(n log n)，是目前最优的解法。

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