草庐IT

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

ppeua 2023-06-05 原文

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;
}

完结撒花：

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

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

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

🌈诸君，山顶见！

单调动态规划xff0cxffxff0算法leetcode贪心算法蓝桥杯

有关【动态规划】最长上升子序列（单调队列、贪心优化）的更多相关文章

  1. ruby - 是否有用于序列化和反序列化各种格式的对象层次结构的模式？ - 2

    给定一个复杂的对象层次结构，幸运的是它不包含循环引用，我如何实现支持各种格式的序列化？我不是来讨论实际实现的。相反，我正在寻找可能会派上用场的设计模式提示。更准确地说:我正在使用Ruby，我想解析XML和JSON数据以构建复杂的对象层次结构。此外，应该可以将该层次结构序列化为JSON、XML和可能的HTML。我可以为此使用Builder模式吗？在任何提到的情况下，我都有某种结构化数据-无论是在内存中还是文本中-我想用它来构建其他东西。我认为将序列化逻辑与实际业务逻辑分开会很好，这样我以后就可以轻松支持多种XML格式。 最佳答案 我最

  2. ruby - 在 Ruby 中动态创建数组 - 2

    有没有办法在Ruby中动态创建数组？例如，假设我想遍历用户输入的书籍数组:books=gets.chomp用户输入:"TheGreatGatsby,CrimeandPunishment,Dracula,Fahrenheit451,PrideandPrejudice,SenseandSensibility,Slaughterhouse-Five,TheAdventuresofHuckleberryFinn"我把它变成一个数组:books_array=books.split(",")现在，对于用户输入的每一本书，我想用Ruby创建一个数组。伪代码来做到这一点:x=0books_array.

  3. ruby - 是否可以将 IRB 提示配置为动态更改？ - 2

    我想在IRB中浏览文件系统并让提示更改以反射(reflect)当前工作目录，但我不知道如何在每个命令后进行提示更新。最终，我想在日常工作中更多地使用IRB，让bash溜走。我在我的.irbrc中试过这个:require'fileutils'includeFileUtilsIRB.conf[:PROMPT][:CUSTOM]={:PROMPT_N=>"\e[1m:\e[m",:PROMPT_I=>"\e[1m#{pwd}>\e[m",:PROMPT_S=>"FOO",:PROMPT_C=>"\e[1m#{pwd}>\e[m",:RETURN=>""}IRB.conf[:PROMPT_MO

  4. ruby - 在 Ruby 中比较序列 - 2

    假设我必须(小型到中型)阵列:tokens=["aaa","ccc","xxx","bbb","ccc","yyy","zzz"]template=["aaa","bbb","ccc"]如何确定tokens是否以相同的顺序包含template的所有条目？(请注意，在上面的示例中，应忽略第一个“ccc”，从而由于最后一个“ccc”而导致匹配。) 最佳答案 这适用于您的示例数据。tokens=["aaa","ccc","xxx","bbb","ccc","yyy","zzz"]template=["aaa","bbb","ccc"]po

  5. ruby-on-rails - carrierwave:在序列化动态属性上安装 uploader - 2

    首先，我使用的是rails3.1.3和来自master的carrierwavegithub仓库的分支。我使用after_init钩子(Hook)来确定基于属性的字段页面模型实例并为这些字段定义属性访问器将值存储在序列化哈希中(希望它清楚我是什么谈论)。这是我正在做的事情的精简版:classPage省略mount_uploader命令让我可以访问我想要的属性。但是当我安装uploader时出现错误消息说“nil类的未定义新方法”我在源代码中读到有方法read_uploader和扩展模块中的write_uploader。我如何必须覆盖这些来制作mount_uploader命令使用我的“虚拟

  6. ruby - 在 Ruby 中动态生成多维数组 - 2

    我正在尝试动态构建一个多维数组。我想要的基本上是这样的(为简单起见写出来):b=0test=[[]]test[b]这给了我错误:NoMethodError:undefinedmethod`test=[[],[],[]]而且它工作正常，但在我的实际使用中，我不会事先知道需要多少个数组。有一个更好的方法吗？谢谢 最佳答案 不需要像您正在使用的索引变量。只需将每个数组附加到您的test数组:irb>test=[]=>[]irb>test[["a","b","c"]]irb>test[["a","b","c"],["d","e","f"]]

  7. ruby-on-rails - 使用 gmaps4rails 动态加载谷歌地图标记 - 2

    如何只加载map边界内的标记gmaps4rails？当然，在平移和/或缩放后加载新的。与此直接相关的是，如何获取map的当前边界和缩放级别？ 最佳答案 我是这样做的，我只在用户完成平移或缩放后替换标记，如果您需要不同的行为，请使用不同的事件监听器:在你看来(index.html.erb):{"zoom"=>15,"auto_adjust"=>false,"detect_location"=>true,"center_on_user"=>true}},false,true)%>在View的底部添加:functiongmaps4rail

  8. ruby - 动态方法链？ - 2

    如何在对象上调用方法名称的嵌套哈希？例如，给定以下哈希:hash={:a=>{:b=>{:c=>:d}}}我想创建一个方法，给定上面的散列，执行以下操作:object.send(:a).send(:b).send(:c).send(:d)我的想法是我需要从一个未知的关联中获取一个特定的属性(这个方法不知道，但程序员知道)。我希望能够指定一个方法链来以嵌套哈希的形式检索该属性。例如:hash={:manufacturer=>{:addresses=>{:first=>:postal_code}}}car.execute_method_hash(hash)=>90210

  9. ruby-on-rails - 在 Elastic Beanstalk 上升级 Ruby - 2

    如何在ELB上设置和更新ruby​​版本？我已经在我们的qa和暂存环境中使用ruby2.2.2大约8个月了。我刚刚在星期一设置我们的生产环境，它不会部署，因为它说ruby​​设置为2.2.3而我的gemfile说2.2.2。我更新并重新部署，一切似乎都很好。我回到了qa/staging环境，但无法将其更新到ruby​​2.2.3。一直说ruby版本是2.2.2，Gemfile是2.2.3我升级了(通过elbui):运行Ruby2.2(PassengerStandalone)的64位AmazonLinux2015.03v1.3.1到运行Ruby2.2(PassengerStandalon

  10. ruby - 如何使用 method_missing 动态声明方法？ - 2

    我有一个ruby​​程序，我想接受用户创建的方法，并使用该名称创建一个新方法。我试过这个:defmethod_missing(meth,*args,&block)name=meth.to_sclass我收到以下错误:`define_method':interningemptystring(ArgumentError)in'method_missing'有什么想法吗？谢谢。编辑:我以不同的方式让它工作，但我仍然很好奇如何以这种方式做到这一点。这是我的代码:defmethod_missing(meth,*args,&block)Adder.class_evaldodefine_method

随机推荐