嘿，这个问题其实就是经典的**最长递增子序列（Longest Increasing Subsequence, LIS）**问题嘛！不管是“找最大规模的有序非连续子集”还是“求最少移除多少元素让剩余列表有序”，本质都是同一个问题——因为LIS的长度就是你能保留的最多元素数量，总元素数减去这个长度就是要移除的最少元素数。我给你梳理两个核心思路，不用写具体代码，好理解得很：

思路一：动态规划基础版（适合小数据量） #

• 先搞一个和输入列表长度一样的dp数组，dp[i]的含义是：以第i个元素结尾的最长递增子序列的长度。
• 逐个遍历列表里的每个元素nums[i]，然后回头检查它前面所有的元素nums[j]（j从0到i-1）：
  • 如果nums[j] < nums[i]，说明当前元素nums[i]可以接在nums[j]的子序列后面，那dp[i]就取dp[j]+1和当前dp[i]里的较大值。
• 等遍历完所有元素，dp数组里的最大值就是LIS的长度。要是想还原出具体的子序列，还得额外记录每个位置的前驱节点，不过只看思路的话，知道长度怎么来就够了。

思路二：贪心+二分查找高效版（适合大数据量） #

这个方法比动态规划快很多，核心是用贪心策略维护一个“最小末尾元素数组”：

• 维护一个tails数组，tails[k]表示长度为k+1的递增子序列的最小末尾元素。这个数组的意义是：相同长度的子序列，末尾元素越小，后续能接上更多元素的概率就越大。
• 逐个遍历输入列表里的元素x：
  • 如果x比tails的最后一个元素大，直接把x加到tails末尾，相当于子序列的长度加1。
  • 如果x不比最后一个元素大，就用二分查找找到tails里第一个大于等于x的位置，把那个位置的元素替换成x。
• 遍历结束后，tails的长度就是LIS的长度。要注意的是，tails数组本身不一定是最终的子序列，但它的长度是对的——如果要还原出像示例里的[1,2,3,6,7,9]，需要额外记录每个元素的来源信息，不过核心思路就是靠贪心+二分来优化效率。

举个你给的例子[1,2,8,3,6,4,7,9,5]，用思路二走一遍的话，tails数组会逐步变成：[1]→[1,2]→[1,2,8]→[1,2,3]→[1,2,3,6]→[1,2,3,4]→[1,2,3,4,7]→[1,2,3,4,7,9]→[1,2,3,4,5,9]，最终长度是6，正好对应示例输出的子序列长度。

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