我懂你这种找不到解决方案的挫败感——刚才特意去谷歌搜了下，确实没找到直接匹配这个需求的现成方案。那我先把问题明确下来，再讲我想到的算法思路，要是你有更优的实现或者不同的想法，欢迎一起讨论！

问题定义 #

给定一个随机无序数组，我们需要从中提取出按原数组顺序排列的严格递增子序列，要求子序列中的每个元素都大于前一个元素，最终得到的子序列如示例所示：

输入数组：{4, 3, 5, 7, 2, 9, 15, 12, 13}
输出子序列：{4, 5, 7, 9, 15}

我的算法思路 #

这个思路非常直接，时间复杂度是O(n)，只需要一次遍历就能完成：

• 初始化一个结果列表，先把数组的第一个元素加入进去。
• 从数组的第二个元素开始遍历：
  • 如果当前元素严格大于结果列表的最后一个元素，就将它添加到结果列表中；
  • 如果当前元素小于或等于结果列表的最后一个元素，直接跳过该元素。
• 遍历结束后，结果列表就是我们需要的子序列。

算法示例推演 #

用你给出的输入数组来走一遍流程：

1. 初始结果列表：[4]
2. 遍历到3：3 ≤ 4，跳过
3. 遍历到5：5 > 4，加入列表 → [4,5]
4. 遍历到7：7 > 5，加入列表 → [4,5,7]
5. 遍历到2：2 ≤7，跳过
6. 遍历到9：9 >7，加入列表 → [4,5,7,9]
7. 遍历到15：15 >9，加入列表 → [4,5,7,9,15]
8. 遍历到12：12 ≤15，跳过
9. 遍历到13：13 ≤15，跳过
   最终得到的结果正好和示例输出一致。

如果你的实际需求是寻找最长递增子序列（LIS）（即不要求连续，但子序列长度最长），那这个简单遍历的方法就不适用了，此时可以采用O(n log n)的优化算法——不过从你的示例输出来看，上面的思路应该正好匹配你的需求。

要是你有更高效的实现思路或者不同的需求解读，欢迎随时补充交流！

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