最长递增子序列

[编程题]最长递增子序列

热度指数：6515 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定数组arr，设长度为n，输出arr的最长递增子序列。（如果有多个答案，请输出其中字典序最小的）

输入描述:

输出两行，第一行包括一个正整数n（n<=100000），代表数组长度。第二行包括n个整数，代表数组arr 。

输出描述:

输出一行。代表你求出的最长的递增子序列。

示例1

输入

9
2 1 5 3 6 4 8 9 7

输出

1 3 4 8 9

示例2

输入

5
1 2 8 6 4

输出

1 2 4

说明

其最长递增子序列有3个，（1，2，8）、（1，2，6）、（1，2，4）其中第三个字典序最小，故答案为（1，2，4）

备注:

时间复杂度，空间复杂度。

算法知识视频讲解

bytedancers

发表于 2021-04-01 19:38:50

class Solution: def LIS(self, arr): stack = [0] n = len(arr) pre = [-1] * n for i in range(1, n): if a 展开全文

总之就是非常可爱

发表于 2022-02-15 21:02:38

#include<bits/stdc++.h> using namespace std; int max(int a,int b){ return a>b?a:b; } int main(){ int n; &n 展开全文

开挂了的菜鸡很想奋斗

发表于 2023-09-03 17:24:08

本题采用类似耐心排序的算法，通过二分查找的方式，将题目的复杂度将为（NlogN)。通过二分查找的方式可以成功地获得最长递增子序列的大小，并保证所得子序列是严格字典序的。该题的难点在于如何获得子序列中的每个元素，我们采用一个index数组记录以序号为i为结尾的最长递增子序列的长度，一个MaxInd数字展开全文