图解一道腾讯笔试算法题：「最长上升子序列」
16lz
2021-01-22
题目描述
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
说明:
可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(nlog n) 吗?
题目解析
首先仔细审题，明确题目中的条件。
1、子序列：不要求连续子序列，只要保证元素前后顺序一致即可；
2、上升：这里的“上升”是“严格上升”，类似于 [2, 3, 3, 6, 7]这样的子序列，因为 3 重复了，所以不是“严格上升”的。
一个序列可能有多个最长上升子序列，题目中只要我们求这个最长的长度。如果使用回溯搜索，选择所有的子序列进行判断，时间复杂度为 ©著作权归作者所有：来自51CTO博客作者mb5fe18fab305a5的原创作品，如需转载，请注明出处，否则将追究法律责任
更多相关文章
- 巩固 | 最全面的算法复杂度分析
- 这道算法题太简单？你忽略了时间复杂度的要求！
- 冰与火之歌：「时间」与「空间」复杂度
- 看动画轻松理解时间复杂度（二）
- 看动画轻松理解时间复杂度（一）
- 时间序列&日期学习笔记大全（上）
- 不会时间序列预测？不要紧，大神来教你
- 详解之php反序列化
- 直击PHP序列化和反序列化原理