首页 > 试题广场 >

最长上升子序列(三)

[编程题]最长上升子序列(三)

给定数组 arr ，设长度为 n ，输出 arr 的最长上升子序列。（如果有多个答案，请输出其中按数值(注：区别于按单个字符的ASCII码值)进行比较的字典序最小的那个）

数据范围： $0 \le n \le 200000 , 0 \le arr_i \le 1000000000$

要求：空间复杂度 $O(n)$ ，时间复杂度 $O(nlogn)$

示例1

输入

[2,1,5,3,6,4,8,9,7]

[1,3,4,8,9]

示例2

[1,2,8,6,4]

[1,2,4]

其最长递增子序列有3个，（1，2，8）、（1，2，6）、（1，2，4）其中第三个 按数值进行比较的字典序 最小，故答案为（1，2，4）

算法知识视频讲解

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

动态规划二分

难度：

0条回答 1729收藏 17041浏览

查看代码

最长上升子序列(三)

扫一扫，把题目装进口袋