网络营销网站建设知识,免费表格模板网站,网站建设的费用和预算,wordpress删除自豪的Halo#xff0c;这里是Ppeua。平时主要更新C语言#xff0c;C#xff0c;数据结构算法......感兴趣就关注我吧#xff01;你定不会失望。 #x1f308;个人主页#xff1a;主页链接 #x1f308;算法专栏#xff1a;专栏链接 我会一直往里填充内容哒#xff01; … 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。循环往复即可
代码实现:
#includeiostream
#includealgorithm
using namespace std;
const int N100010;
int n;
int a[N];
int q[N];int main()
{cinn;for(int i0;in;i){cina[i];}int len0;q[0]-2e9;for(int i0;in;i){int l0,rlen;while(lr){int midlr11;if(q[mid]a[i])lmid;else rmid-1;}lenmax(len,r1);q[r1]a[i];}coutlen;return 0;
}
完结撒花 本篇博客的内容【动态规划最长上升子序列单调队列、贪心优化】已经结束。 若对你有些许帮助可以点赞、关注、评论支持下博主你的支持将是我前进路上最大的动力。 若以上内容有任何问题欢迎在评论区指出。若对以上内容有任何不解都可私信评论询问。 诸君山顶见
