最长上升子序列优化（贪心+二分）（超级详细的讲解）-程序员宅基地

技术标签：算法 # DP与贪心题目

最长上升子序列优化（贪心+二分）

一、回顾
- 1、问题描述
- 2、动规代码弊端
二、优化
- 1、算法优化
- 2、代码实现

一、回顾

1、问题描述

在这里插入图片描述

2、动规代码弊端

我们之前的动规代码的时间复杂度是 $O(n^2)$ 。如果大家还不知道动态规划的逻辑的话，建议大家先去看一下动态规划的解决思路：动态规划解决最长上升子序列

虽然动态规划的思路已经比DFS的做法快了很多，但是当数据量增大以后， $O(n^2)$ 的时间复杂度还是会超时的，那么我们能否进一步优化呢？

我们接着往下看。

二、优化

1、算法优化

我们先看下面的例子：
在这里插入图片描述
上述红色部分是最长上升子序列。

我们发现：

第一个元素 $1$ ，就是长度为 $1$ 的所有子序列中最小的最后一个元素。

第二个元素 $2$ ，就是长度为 $2$ 的所有子序列中最小的最后一个元素。

第三个元素 $5$ ，就是长度为 $3$ 的所有子序列中最小的最后一个元素。

第四个元素 $6$ ，就是长度为 $4$ 的所有子序列中最小的最后一个元素。

我们现在想一想，这是为什么呢？

我们长度为 $(l e n + 1)$ 的子序列，是在长度为 $(l e n)$ 的子序列的基础上发展而来的。

而我的子序列能否边长，其实是取决于子序列的最后一位。

最后一位越小，我的子序列越容易变长。

我们可以简单证明一下：

假设我们的最长上升子序列的长度是 $l e n$ ，而该序列中的前 $k$ 个元素组成的子序列中（ $a [k]$ 是这个子序列的最后一位）， $a [k]$ 不是最小的那一位，即存在一个以 $j$ 为结尾的长度为 $k$ 的子序列（两个子序列只有最后一位不同），并且 $j < a [k]$ ，同时这个序列并不是最终答案的一部分。

由于答案是严格单调增的序列，那么必定存在 $a [k - 1] < a [k] < a [k + 1]$ ，又因为两个长度为 $k$ 的子序列只有最后一位不同，所以必定满足 $j > a [k - 1]$ 。

那么此时必定存在以下等式：

$a [k - 1] < j < a [k] < a [k + 1]$

也就是说，我们可以将我们假想的 $j$ 插入到答案中，使得其长度变成 $(l e n + 1)$ 。而我们假设最大就是 $l e n$ ，可是我们却推导出了一个比 $l e n$ 更大的上升子序列。所以产生了矛盾，假设不成立。

因此，我们得出结论：

最长上升子序列中的某一位 $a [i]$ ，必定是长度为 $i$ 的子序列的最后一位中，最小的一个。

所以，我们维护这样一个数组 $q [i]$ 。

这个数组记录的是子序列长度为 $i$ 的序列中，最后一位中最小的最后一位。如果我们碰到了一个 $a [i]$ 。

同时，这个 $a [i]$ 满足 $q [k] < a [i] < q [k + 1]$ 。

此时，就说明这个 $a [i]$ 是可以接在长度为 $k$ 的子序列后面，从而让这个序列的长度变成 $(k + 1)$ 。

而此时的 $a [i] < q [k + 1]$ ，说明长度为 $k + 1$ 的子序列中，又出现了一个比原最小值更小的 $a [i]$ 。

所以我们此时更新一下： $q [k + 1] = a [i]$ 。

于是目前的问题，就是我们遍历到一个数值的时候，我们要立刻找到 $q [k]$ 和 $q [k + 1]$ :

使得 $q [k] < a [i] < q [k + 1]$

而经过我们刚才的分析，其实遍历过后，这个 $q [N]$ 数组就是我们的最长的上升子序列的具体内容，所以这个序列必定是升序的。

而对于有序的序列，我们可以采用二分法来解决。

2、代码实现

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N],q[N];
int n;
int main()
{
    
    scanf("%d", &n);
    //读入数据
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    
    int len = 0;//记录长度
    
    for (int i = 0; i < n; i ++ )
    {
    
        int l = 0, r = len;
        while (l < r)
        {
    
            int mid = l + r + 1 >> 1;
            if (q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        //如果该元素插在了末尾，说明r+1=len+1了。此时长度增加，我们更新len 
        len = max(len, r + 1);
        q[r + 1] = a[i];
    }
    printf("%d\n", len);
    return 0;
}

本文链接：https://blog.csdn.net/weixin_72060925/article/details/128429202

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

获得硬盘ID（序列号、机器码）的C++代码源码_硬盘id获取 c++-程序员宅基地

文章浏览阅读612次。获得硬盘的序列号(ID/机器码)的C++源码_硬盘id获取 c++

VRRP协议介绍_vrrp是什么协议-程序员宅基地

文章浏览阅读1w次，点赞5次，收藏60次。1.VRRP的工作原理2.Master路由器和Backup路由器3.VRRP报文格式4.虚拟路由器中的虚拟IP地址和虚拟MAC 地址_vrrp是什么协议

Google Earth Engine谷歌地球引擎GEE栅格代数与NDVI波段计算手动求取_gee波段计算-程序员宅基地

文章浏览阅读2.9k次，点赞2次，收藏15次。本文主要对GEE中的栅格代数与波段计算操作加以介绍。本文是谷歌地球引擎（Google Earth Engine，GEE）系列教学文章的第六篇，更多GEE文章请参考专栏：GEE学习与应用（https://blog.csdn.net/zhebushibiaoshifu/category_11081040.html）。首先，依据第二篇GEE教学博客（https://blog.csdn.net/zhebushibiaoshifu/article/details/117296956）中内容，我们将Lands_gee波段计算

Vue2+Vue3（脚手架）_vue2对应的脚手架版本-程序员宅基地

文章浏览阅读1.3k次，点赞33次，收藏36次。组件化编码流程： (1).拆分静态组件：组件要按照功能点拆分，命名不要与html元素冲突。 (2).实现动态组件：考虑好数据的存放位置，数据是一个组件在用，还是一些组件在用： 1).一个组件在用：放在组件自身即可。放在他们共同的父组件上（状态提升）。 (3).实现交互：从绑定事件开始。props适用于： (1).父组件 ==> 子组件通信 (2).子组件 ==> 父组件通信（要求父先给子一个函数）_vue2对应的脚手架版本

大数据可视化设计师丹尼斯_自助数据可视化设计师如何谋生-程序员宅基地

文章浏览阅读1.5k次。大数据可视化设计师丹尼斯重点 (Top highlight)I hit a point in my life where I could take my career in countless directions. I left my job in the summer of 2019 and began my venture as a freelancer. I work part-time..._hit a point

iOS 富文本之Label前后加文字“标签”_ios 字符串最后跟标签-程序员宅基地

文章浏览阅读2.1k次。先看需求图吧解析一下，title的文字换行，title前面加标签，这样的情况一般就会想到用NSMutableAttributedString富文本来解决，富文本的图文混排可以完美解决这个问题。但是，后台帅哥哥告诉本宝宝了，title前面的标签给返回的是文字，并不是图片……GG了……富文本可以指定部分文字的背景颜色，但是要求的这个标签有背景，也有圆角，没办法解决了。只有View..._ios 字符串最后跟标签

随便推点

C语言时间汇总_竞赛在排名时,一般是按做题数排名,但当做题数相同时,则按做各题所花总时间进行排-程序员宅基地

文章浏览阅读1k次。题目描述竞赛在排名时，一般是按做题数排名，但当做题数相同时，则按做各题所花总时间进行排名。下面编程实现时间的汇总。输入先输入一个ｎ（１＜＝ｎ＜＝１０），表示总共做出了ｎ题。然后输入ｎ个做出各题所花的时间，格式为HH:MM:SS，其中，HH表示时（00<=HH<10），MM表示分（00<=MM<=59）,SS表示秒（00<=SS<=59）。输出输出将..._竞赛在排名时,一般是按做题数排名,但当做题数相同时,则按做各题所花总时间进行排

linux启动 profile,Linux 启动时profile、bashrc、~/.bash_profile、~/.bashrc、~/.bash_profile执行顺序以及文件说明...-程序员宅基地

文章浏览阅读1.7k次。Linux 启动时profile、bashrc、~/.bash_profile、~/.bashrc、~/.bash_profile执行顺序以及文件说明一、执行顺序登录linux时，/etc/profile、~/.bash_profile等几个文件的执行过程。如图所示:二、在登录Linux时要执行文件的过程如下：在刚登录Linux时，首先启动 /etc/profile 文件，然后再启动用户目录下的 ..._怎么运行profile文件

python中的group,match-程序员宅基地

文章浏览阅读1.1w次，点赞7次，收藏16次。正则表达式中，group()用来提出分组截获的字符串，（）用来分组import rea = "123abc456"print re.search("([0-9]*)([a-z]*)([0-9]*)",a).group(0) #123abc456,返回整体print re.search("([0-9]*)([a-z]*)([0-9]*)",a).group(1)

解决 jQuery 中使用双引号的问题_jquery 给元素赋值带双引号-程序员宅基地

文章浏览阅读174次。在编写 jQuery 代码时，有时候会遇到使用双引号的情况，但双引号在 jQuery 中有特殊的含义。如果你使用的是 ES6 或更高版本的 JavaScript，你可以使用模板字符串来解决这个问题。这些是解决 jQuery 中使用双引号的常见方法。无论你选择哪种方法，都能解决在 HTML 方法中使用双引号的问题，并使你的代码能够正常工作。在上面的示例中，我们在双引号前添加了一个反斜杠，这样 jQuery 就能正确解析字符串。在上面的示例中，我们使用模板字符串来定义包含双引号的 HTML 字符串。_jquery 给元素赋值带双引号

HTTP超详细教程_http传输流程-程序员宅基地

文章浏览阅读9.7k次，点赞48次，收藏124次。HTTP是超文本传输协议（Hypertext Transfer Protocol）的缩写，是一种用于传输数据的协议。它是基于TCP/IP协议的应用层协议，通常用于Web浏览器和Web服务器之间的通信。HTTP协议的主要特点是简单、灵活、易于扩展和支持多媒体等不同类型的数据传输。_http传输流程

MVC3学习随记一-程序员宅基地

文章浏览阅读90次。最近才接触mvc，也是才接触linq语法，还有EntiyFramework，个人感觉这种开发模式还是挺不错的，随手记点笔记，简单做个增删改查吧一、实例化上下文ObjectContext：引用空间那些就跳过了。。db_testEntities test = new db_testEntities();二、用linq语法从数据库查询数据：使用linq语句查询返回的..._testentities的引用空间