如何实现删除最少元素得到升序数字序列的算法

你要解决的「删除最少元素得到升序序列」问题，本质就是求原序列的最长严格上升子序列（LIS）：原序列长度减去最长上升子序列的长度，就是最少需要删除的元素数量。 #

这里提供两种常用实现，你可以根据序列长度选择：

1. 动态规划实现（O(n²)复杂度，适合长度1000以内的短序列） #

核心逻辑：

• 定义dp[i]表示以第i个元素结尾的最长严格上升子序列长度
• 额外用prev数组记录每个位置的前序元素下标，用于回溯得到最终序列
• 双重遍历计算dp数组最大值，再回溯得到完整子序列

2. 贪心+二分优化实现（O(nlogn)复杂度，适合长度1000以上的长序列） #

这个方案是工业界最常用的高效实现，对应你给的示例测试代码如下：

def longest_increasing_subsequence(nums):
    if not nums:
        return []
    tails = []
    pos = []
    prev = [-1] * len(nums)
    
    for i, x in enumerate(nums):
        # 二分查找替换位置
        left, right = 0, len(tails)
        while left < right:
            mid = (left + right) // 2
            if tails[mid] < x:
                left = mid + 1
            else:
                right = mid
        # 更新tails数组
        if left == len(tails):
            tails.append(x)
        else:
            tails[left] = x
        pos.append(left)
        # 记录前驱索引用于回溯
        if left > 0:
            for j in range(i-1, -1, -1):
                if pos[j] == left - 1 and nums[j] < x:
                    prev[i] = j
                    break
    # 回溯得到完整子序列
    res = []
    max_pos = len(tails) - 1
    idx = pos.index(max_pos)
    while idx != -1:
        res.append(nums[idx])
        idx = prev[idx]
    return res[::-1]

# 测试示例
wrong_sequence = [1,2,8,88,99,1,18,77,78,100,103]
print(longest_increasing_subsequence(wrong_sequence))
# 输出结果：[1, 2, 8, 18, 77, 78, 100, 103]，和你预期的正确结果完全一致

如果你的业务场景允许非严格升序（即相等元素可以保留），只需要把二分判断条件中的tails[mid] < x修改为tails[mid] <= x即可。

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