最长递增子序列(LIS)[通俗易懂]

最长递增子序列(LIS)[通俗易懂]①dp[i]表示以i为结尾的最长子序列长度②dp[i]表示长度为i的最长递增子序列末尾的数

大家好,又见面了,我是你们的朋友全栈君。

最长递增子序列(LIS)

问题描述:

求一个序列的最长递增子序列,这样的子序列是允许中间越过一些字符的,即留“空”。

例如:4 2 3 1 5 的最长递增子序列为 2 3 5,长度为 3 。

解法:

这里给出两种动态规划的做法,第二种是比较优化的 dp 。

① dp:dp[i] 表示以 i 结尾的最长递增子序列长度
在这里插入图片描述
第一个元素直接设置 LIS 长度为 1 即可。
在这里插入图片描述
处理第二个元素 2 的时候判断是否比前面的元素 4 大,没有的话那么以 2 为结尾的 LIS 就是 2,

即 LIS 长度为 1。
在这里插入图片描述
处理第三个元素 3 的时候需要跟前面的每个元素都进行比较,3 大于 2,则 LIS 的长度可能为 dp[1] + 1,

3 小于 4,则 LIS 的长度可能为 1,比较dp[1] + 1 和 1,取最大值,为 2 。
在这里插入图片描述
处理第四个元素 1,发现比前面的元素都小,那么以 1 为结尾的 LIS 只可能为 1,因此 LIS 的长度为 1。
在这里插入图片描述
处理最后一个元素 5,发现比前面的元素都大,那么以 5 结尾的 LIS 的长度可能为

dp[0] + 1,dp[1] + 1,dp[2] + 1,dp[3] + 1。

其中的最大值为 dp[2] + 1 = 3,因此 LIS 的长度为 3。

总结:

dp[i] 默认都为 1,因为以 i 结尾的 LIS 至少包含自己。

在 dp 表 0~i-1 中比对时,若 arr[i] > arr[j],

那么 dp[j] + 1 可能为 dp[i] 的最终值。

需要在所有的可能值中取最大值。

时间复杂度为 O(n2)。

② dp:dp[i] 表示长度为 i 的最长递增子序列(LIS)末尾的数
在这里插入图片描述
第一个元素直接加入 dp 表,dp[1] = 4,表示长度为 1 的 LIS 末尾的数当前为 4。
在这里插入图片描述
第二个元素为 2,因为 2 < 4,直接替换掉 4,dp[1] = 2 。

因为后面序列中的数字 > 2 的几率一定比 > 4 的几率高,有种贪心的感觉。
在这里插入图片描述
第三个元素为 3,由于 3 > dp[1] = 2,构成递增,dp[2] = 3,表示长度为 2 的 LIS 的末尾为 3 。
在这里插入图片描述
第四个元素为 1,由于 1 < dp[2] = 3,因此在前面一定有一个位置可以换成 1,

并且后面的递增性质不会被破坏。

第一个 > 1 的为 dp[1] = 2,因此将 dp[1] 置为 1。
在这里插入图片描述
最后一个元素为 5, 5 > dp[2] = 3,构成递归,故dp[3] = 5。

全部遍历完成,这个时候我们就可以发现 dp 数组的下标 3 就是我们要求的 LIS 长度。

参考代码:

// 这里的最长递增子序列是允许中间跨越其他子序列的 
#include<iostream>
#include<algorithm>
using namespace std;
int *arr;
int *dp;
// 经典问题 dp[i]的意思为以i为结尾的最长子序列为多少 
int getResult(int n)
{ 

dp[0] = 1;
for (int i = 1; i < n; i++)
{ 

int cnt = 1;
for (int j = i - 1; j >= 0; j--)
{ 

if (arr[i] > arr[j])
{ 
  // 保证递增 
cnt = max(cnt, dp[j] + 1);
}
}
dp[i] = cnt;
}
int ans = 0;
for (int i = 0; i < n; i++)
{ 

ans = max(ans, dp[i]);
}
return ans;
}
// 二分查找变体 找到第一个大于等于n的位置index 
int BinarySearch(int *dp, int len, int n)
{ 

int left = 1;
int right = len;
while (left < right)
{ 

int mid = (left + right) / 2;
if (dp[mid] >= n)
{ 

right = mid;
}
else
{ 

left = mid+1;
}
}
return right;
}
// 优化的dp dp数组的最终下标为答案 
int getResult1(int n)
{ 

dp[1] = arr[0];
int index = 1;
for (int i = 1; i < n; i++)
{ 

if (arr[i] > dp[index])
{ 

// 更新index 
dp[++index] = arr[i];
}
else
{ 

// 把dp数组中第一个大于等于n的数字替换为arr[i] 
int tempIndex = BinarySearch(dp, index, arr[i]);
dp[tempIndex] = arr[i];
}
}
return index;
} 
int main(){ 

int n;
while (cin >> n)
{ 

arr = new int[n];
dp = new int[n+1]; 
for (int i = 0; i < n; i++)
{ 

cin >> arr[i];
}
int ans = getResult1(n);
cout << ans << endl;
delete[] arr;
delete[] dp;
}
return 0;
} 

【END】感谢观看

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/130060.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • sqlserver 日期转字符串_sql server 字符串截取

    sqlserver 日期转字符串_sql server 字符串截取最近实习项目中需要用到sqlserver数据库,于是安装了之后使用了一下,觉得基本的sql语句是差不多的,区别就是给的函数不一样。在开发中遇到一个需求,需要将时间戳转化为datetime类型,具体如下:—-&gt;datetime我一开始百度之后发现是这样写:selectCONVERT(VARCHAR(20),DATEADD(SECOND,1533812469,…

  • echart横坐标字体样式问题 xAxis属性问题

    echart横坐标字体样式问题 xAxis属性问题

  • java键盘钩子_jna test【鼠标 键盘钩子】「建议收藏」

    java键盘钩子_jna test【鼠标 键盘钩子】「建议收藏」jna4.5简单实现后台键盘事件通过jna实现在后台运行,当屏幕按下相对应的按钮时JAVA实现鼠标钩子的源代码仅用JAVA实现全局鼠标钩子的功能,很好很超强,学习下java全局按键键盘钩子java鼠标按键钩子,内含test.java使用实例,hook文件夹是写好的钩子,放到项目源文件下,直接调用。两个jar包是必须建立到项目中的c#Wpf简单鼠标钩子实例一个简单的鼠标钩子例子帮助初学者掌握。基于…

  • MATLAB GUI设计之弹出式菜单的使用

    MATLAB GUI设计之弹出式菜单的使用弹出式菜单在MATLABGUI设计中常常出现。比如串口助手、绘制图形等经常见到弹出式菜单如下图所示:使用方法:一、准备工作1、从MATLABGUIDE中拖出一个弹出式菜单2、双击这个弹出式菜单,出现检查器:将注意力放在途中红线位置处,点击string处的图标将其中的内容修改为你想要显示的内容:tag处的内容修改为自己想管这个弹出式菜单的名字。这里就按照原来

  • pycharm逐行调试时跳过了某行的解决办法[通俗易懂]

    pycharm逐行调试时跳过了某行的解决办法[通俗易懂]1.首先说原因我遇到的:是由于该行的函数,有装饰器(或者说闭包)装饰它。2.场景再现如图,在逐行调试的时候,我迫切想要知道第98行调试时所返回的内容,而且我还想进入98行的函数内,看看内部到底发生了什么。然而,当我点击StepOver调试下一行的时候,该死的蓝色调试框,跳到了第99行。3.如何解决此时我已经结束了本次debug,当我自己点进第98行的函数进去看的时候,发现没错,函数套了个@response_parser的装饰器,只要有这个装饰器存在,而且我debug时,跳过了该行。

  • Java数据类型及最大值_javaint最大值

    Java数据类型及最大值_javaint最大值YDOOK:Python3.9:YDOOKJYLin1.原理方法:1.“2.实例代码:a_list=[1,2,3,4,5,6,7,8,9,10]print(‘a_list=’,a_list)a_list.append(11)print(‘a_list=’,a_list)3.运行结果:在这里插入代码片

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号