最长上升子序列(LIS)

目录


输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。

说明:

  • 可能会有多种最长上升子序列的组合,你只需要输出对应的长度即可。
  • 你算法的时间复杂度应该为 O(n^2)

进阶: 你能将算法的时间复杂度降低到 O(N*logN) 吗?

1. 方法一:动态规划

定义状态:dp[i] 表示以第 i 个数字为结尾的最长上升子序列的长度。即在 [0, ..., i] 的范围内,选择 以数字 nums[i] 结尾 可以获得的最长上升子序列的长度。注意:以第 i 个数字为结尾,即 要求 nums[i] 必须被选取。反正一个子序列一定会以一个数字结尾,那我就将状态这么定义,这一点是常见的。

状态转移方程:遍历到索引是 i 的数的时候,我们应该把索引是 [0, ... ,i - 1] 的 dp 都看一遍,如果当前的数 nums[i] 严格大于之前的某个数,那么 nums[i] 就可以接在这个数后面形成一个更长的上升子序列。把前面的 i 个数都看了,dp[i] 的值就是它们的最大值加 1 。即比当前数要小的那些里头,找最大的,然后加 1 。

于是状态转移方程是:dp(i) = max{1 + dp(j) if j < i and dp[i] > dp[j]}。

最后不要忘了,扫描一遍这个 dp 数组,其中最大值的就是题目要求的最长上升子序列的长度。

nums = [1,7,9,8,3,4,5]
# dp = [1,2,3,3,2,3,4]  # 可以用于输出最长子序列——基于现有评分列表,计算当前item的排名
dp = [1] * len(nums)
for i in range(1, len(nums)):
    for j in range(i):
        if nums[j] < nums[i]:  # 如果要求非严格递增,将此行 '<' 改为 '<=' 即可。
            dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))

[3, 2, 4]
1
2

2. 方法二:贪心算法(二分法)

思路:每一次来一个新的数 num,在 tail 数组(tail 数组的定义在下面的示意图中有)中找大于等于 num 的那个数,试图让它变小,以致于新来的数有更多的可能性接在它后面,成为一个更长的“上升子序列”,这是“贪心算法”的思想。

在 tail 数组中找大于等于 num 的那个数,可以使用“二分法”

推荐这些文章:

最长不下降子序列(LIS)问题

再解问题前,我们先看题目:

 我们模拟一下程序的运行过程。可以看到a数组中的 -1 对应dp数组的是1,是因为在a数组中-1的前面没有比-1小的数,而a数组中的3对应的dp数组是3,是因为在3的前面(包括它自己)有3个<=它的数(1和2)。后面的以此类推。

这个问题的状态转移方程是:

1 if(a[i]>=a[j]&&(dp[j]+1>dp[i]))//状态转移方程
2 {
3 dp[i]=dp[j]+1;//执行的操作
4 }

 
 
完整程序是这样的:

1 #include<bits/stdc++....

LIS最长上升子序列

首先需要知道,子串和子序列的概念,我们以字符子串和字符子序列为例,更为形象,也能顺带着理解字符的子串和子序列:
(1)字符子串指的是字符串中连续的n个字符,如abcdefg中,ab,cde,fg等都属于它的字串。
(2)字符子序列指的是字符串中不一定连续但先后顺序一致的n个字符,即可以去掉字符串中的部分字符,但不可改变其前后顺序。如abcdefg中,acdg,bdf属于它的子序列,而bac,dbfg则不是,因为它们与字符串的字符顺序不一致。
O(n^2)的DP,O(nlogn)的二分+贪心法,以及O(nlogn)的树状数组优化的DP。
 

...

LIS——最长递增子序列问题

最长递增子序列,举一个例子:
A={5,6,7,4,2,8,3},它的最长递增子序列是5,6,7,8.
转载一下大佬写的吧,大佬写的真的好,好好学习一下,认真体会:https://blog.csdn.net/ltrbless/article/details/81318935
真题实战:http://lx.lanqiao.cn/problem.page?gpid=T73。
这个题我们要知道一点:
最少下降子序列的个数(最少的拦截系统)=最长不下降子序列的长度(重点)
我采取的dp做法,所以就用dp来讲讲:

#include<bits/stdc++.h>
using namesp...

最长不下降子序列(LIS)问题解题思路

题目描述:OpenJudge - 2757:最长上升子序列
要解决这个问题,我们就得明白这个问题用什么思路来解决,无非就是一个一个判断是否符合标准。主要就是这一个动态转移方程式:

a[i]>=a[j]&&(dp[j]+1>dp[i])

在判断后,如果是,则将其设置为之前的数加一:

dp[i]=dp[j]+1;

在每次子循环后,将最大数设为答案:

ans=max(ans,dp[i]);

接下来,整个程序就简单了,再在前面加上数据输入,后面加上输出就完事了,上代码:

1 #include<bits/stdc++.h>
2 using na...

|LIS| = 3(最长上升子序列,DP)

题意
求满足下列条件的序列个数:

长度为\(n\)
序列的每个元素值都在\([1,m]\)
最长严格上升子序列的长度恰好为\(3\)

数据范围
\(3 \leq n \leq 1000\)
\(3 \leq m \leq 10\)
思路
首先回顾一下最长上升子序列的做法:

维护一个vector,记为\(L\)
对于每个元素\(A_i\),找到满足\(L_j \geq A_i\)的最小元素的下标(二分)。如果存在的话,用\(A_i\)替换\(L_j\)。否则,将\(A_i\)添加到\(L\)的后面。
最终\(L\)的长度。

因为我们只关心长度小于等于\(3\)的最长上升子序列。因此考虑...

求出所有LIS的可行起点

在做到codeforces1488E Palindromic Doubles 的时候,需要求出一段序列所有LIS的可行起点,没学过相关的做法,自己想了一个。
假设我们已知一个lis数组,其中lis[i]代表以a[i]结尾的最长LIS,vis[i]=true代表a[i]可以是某条LIS的其中一点,Max[i]代表lis值等于i时的最大值。
则对于a[i],当 j>i && lis[j]=lis[i]+1 && Max[lis[j]]>a[i] 时,vis[i]=true;
这样将数组从后往前枚举,同时维护vis,Max,最后求出的vis数组中,如果...

D1. Kirk and a Binary String (easy version)

hard version 的 On 做法我老早就(通过看题解)弄懂了,但 easy version 的 n2 暴力直到现在才想明白。。。
题意:
给定一个01串,尽量把1改成0,要求任意子区间的LIS长度保持不变。
串长2000
思路:
若把某个1改成0之后,以它为左端点的所有子区间的 LIS 长度保持不变,那就可以改。解释:
对某个固定的 \(L\),把 \(s_L\) 从1改成0后 \(\forall R\in[L,n],\text{LIS}(L,R)\) 的长度不变 \(\iff \text{LIS}(L,R)\) 都是以1而非0开头 \(\iff\) 在 \([L,R]\) 中存在一...

LIS(最长上升子序列)模板

一:

1 #include<bits/stdc++.h>
2 #define INF 0x3f3f3f3f
3 #define MAXN 50000
4 #define ia (i+1)%2
5 #define ib i%2
6 typedef long long ll;
7 using namespace std;
8 int dp[MAXN],a[MAXN];
9 int ans;
10 int LIS(int *a,int n)
11 {
12 int k=0;
13 dp[0]=a[0];
14 for(int i=1;i&l...

动态规划之最长递增子序列

给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1:
输入:nums = [10,9,2,5,3,7,101,18] 输出:4 解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。 示例 2:
输入:nums = [0,1,0,3,2,3] 输出:4 示例 3:
输入:nums = [7,7,7,7,7,7,7] 输出:1
提示:
1 <= nums.length <= 2500 -...

leetcode 376. 摆动序列

解法1:贪心。
除去中间单调的节点即可。
class Solution {
public int wiggleMaxLength(int[] nums) {
int n=nums.length;
int ans=1;
int prevSub=0;
for(int i=1;i<n;i++){
int sub=nums[i]-nums[i-1];
if((sub<0&&prevSub>=0)||(sub>0&&prevS...

文章标题:最长上升子序列(LIS)
文章链接:https://www.dianjilingqu.com/4361.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>