运维开发网

图解一道腾讯笔试算法题:「最长上升子序列」

运维开发网 https://www.qedev.com 2021-01-24 11:09 出处:51CTO 作者:mb5fe18fab305a5
题目描述给定一个无序的整数数组,找到其中最长上升子序列的长度。示例:输入: [10,9,2,5,3,7,101,18]输出: 4 解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。说明:可能会有多种最长上升子序列的组合,你只需要输出对应的长度即可。你算法的时间复杂度应该为 O(n2) 。进阶: 你能将算法的时间复杂度降低到 O(nlog n) 吗?题目解析首先仔细审题,明确题目中

题目描述

给定一个无序的整数数组,找到其中最长上升子序列的长度。

示例:

输入: [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 重复了,所以不是“严格上升”的。

一个序列可能有多个最长上升子序列,题目中只要我们求这个最长的长度。如果使用回溯搜索,选择所有的子序列进行判断,时间复杂度为

扫码领视频副本.gif

0

精彩评论

暂无评论...
验证码 换一张
取 消

关注公众号