首页 > 试题广场 >

最长递增子序列

[编程题]最长递增子序列
  • 热度指数：13002 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

对于一个数字序列，请设计一个复杂度为O(nlogn)的算法，返回该序列的最长上升子序列的长度，这里的子序列定义为这样一个序列U1，U2...，其中Ui < Ui+1，且A[Ui] < A[Ui+1]。

给定一个数字序列A及序列的长度n，请返回最长上升子序列的长度。

测试样例： 
[2,1,4,3,1,5,6],7
返回：4
算法知识视频讲解
开通博客
头像 重生之我要当分子
发表于 2024-12-31 23:49:16
解题思路 这是一个最长上升子序列(LIS)问题，使用二分查找优化。关键点： 贪心策略： 维护一个递增数组 表示长度为 的上升子序列的最小末尾元素 二分查找： 对于每个数字，在 中找到第一个大于它的位置 更新该位置的值为当前数字 结果： 数组的长度就是最长上升子序列的长 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

动态规划 查找
来自：面试常考算法题(九)-...
难度：
76条回答 37412浏览

热门推荐

通过挑战的用户

查看代码

相关试题

最长递增子序列

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号