【动态规划】最长上升子序列（单调队列、贪心优化）

Halo，这里是Ppeua。平时主要更新C语言，C++，数据结构算法......感兴趣就关注我吧！你定不会失望。

 

🌈个人主页：主页链接

🌈算法专栏：专栏链接

     我会一直往里填充内容哒！

🌈LeetCode专栏：专栏链接 

    目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目，也会当天做完发出

🌈代码仓库：Gitee链接

🌈点击关注=收获更多优质内容🌈

目录

题目:最长上升子序列

题解:

代码实现:

完结撒花：

---

本篇是对最长上升子序列基础做法的一种优化，没有看过基础做法的uu们可以看看这篇：最长上升子序列 

题目:最长上升子序列

题解:

优化的做法与之前相比，适用范围更广，当数据范围大的时候，基础做法会TLE。

但优化做法Dp的思想却少了，更像是一种贪心，由于本题是从DP衍生出来的，所以仍然将其归为DP。

废话不多说。

朴素做法为，找到前一个小于当前值，将其最长上升子序列加一，就为当前值得最长上升子序列。

但观察每一个被插入得值，例如有以下五个数字

3和1都为上升序列为1的数组，但能插入到1上的一定能插到三的上面，反之却不一定。所以我们可以想象出，只要保存上升序列长度中最小的那个值最为末端就可以了。

例如这里的3和1都为长度为1的上升序列，但我们只要保存1.

 

之后再将2插入到1上，此时更新上升序列长度为2的最后一个值为2.

4又可以插入到2后，所以更新长度为3的最后一个值为4。

 

最后如图所示

所以我们很容易就能归纳出上面的过程，找到最大小于待插入数的序列，在下一个位置更新其序列长度与队尾的值。

分析下代码实现，len为当前最长的子序列，利用二分查找寻找，最大的小于当前值x的位置，之后将下一个最长子序列的末位更新为x。循环往复即可

代码实现:

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int n;
int a[N];
int q[N];int main()
{cin>>n;for(int i=0;i<n;i++){cin>>a[i];}int len=0;q[0]=-2e9;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;}len=max(len,r+1);q[r+1]=a[i];}cout<<len;return 0;
}

完结撒花：

🌈本篇博客的内容【动态规划：最长上升子序列（单调队列、贪心优化）】已经结束。

🌈若对你有些许帮助，可以点赞、关注、评论支持下博主，你的支持将是我前进路上最大的动力。

🌈若以上内容有任何问题，欢迎在评论区指出。若对以上内容有任何不解，都可私信评论询问。

🌈诸君，山顶见！