算法——动态规划

一、

53. 最大子数组和 - 力扣(LeetCode)

最大子数组和,可以建立一个dp表,来存放当前的位置的累加的最大和

int maxSubArray(vector<int>& nums) {int n=nums.size();if(n==1)return nums[0];vector<int> dp(n);int sum=0;if(nums[0]>0)dp[0]=nums[0];//大于0就直接放入elsedp[0]=0;//小于0就放入0for(int i=1;i<n;i++){int sum=dp[i-1]+nums[i];if(sum>0)dp[i]=sum;else dp[i]=0;}sort(dp.begin(),dp.end());if(dp[n-1]<=0){sort(nums.begin(),nums.end());return nums[n-1];}return dp[n-1];}

二、

918. 环形子数组的最大和 - 力扣(LeetCode)

这样就是将求数组的连续最大值转换为求数组的最小值

那么我们就需要建立两个表,一个是f表,用来存最大值的,一个是g表,用来存最小值的。

int maxSubarraySumCircular(vector<int>& nums) {int n=nums.size();vector<int> f(n+1),g(n+1);//定n+1 是为了防止i-1的时候越界int fmax=INT_MIN,  gmin=INT_MAX, sum=0;for(int i=1;i<=n;i++){int x=nums[i-1];f[i]=max(x,x+f[i-1]);fmax=max(fmax,f[i]);//实时读取最大值g[i]=min(x,x+g[i-1]);gmin=min(gmin,g[i]);sum+=x;}return sum==gmin?fmax:max(fmax,sum-gmin);//如果sum==gmin说明数组里全是负数}

三、

152. 乘积最大子数组 - 力扣(LeetCode)

 int maxProduct(vector<int>& nums) {int len=nums.size();vector<int> pos(len);auto nag=pos;nag[0]=nums[0],pos[0]=nums[0];for(int i=1;i<len;i++){pos[i]=max(pos[i-1]*nums[i],max(nums[i],nag[i-1]*nums[i]));nag[i]=min(nag[i-1]*nums[i],min(nums[i],pos[i-1]*nums[i]));}sort(pos.begin(),pos.end());sort(nag.begin(),nag.end());return max(pos[len-1],nag[len-1]);}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/154391.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【办公自动化】在Excel中按条件筛选数据并存入新的表2.0(文末送书)

&#x1f935;‍♂️ 个人主页&#xff1a;艾派森的个人主页 ✍&#x1f3fb;作者简介&#xff1a;Python学习者 &#x1f40b; 希望大家多多支持&#xff0c;我们一起进步&#xff01;&#x1f604; 如果文章对你有帮助的话&#xff0c; 欢迎评论 &#x1f4ac;点赞&#x1f4…

利达卓越:绿色金融助推经济高质量发展

随着环境问题的日益突出和可持续发展的需求增加,绿色金融将成为金融发展的重要方向之一。政府、金融机构、企业和公众都将加大对绿色金融的支持和关注,绿色金融也将更加成熟和规范。利达卓越积极推动绿色金融的快速发展,为实现可持续发展目标提供了重要支持。绿色金融将成为金融…

uni-app生命周期

uni-app的生命周期包括&#xff1a;应用生命周期、页面生命周期、组件生命周期 一、应用生命周期&#xff08;只能在App.vue文件中监听&#xff09; 函数说明onLaunch初始化完成时触发&#xff08;全局只触发一次&#xff09;onShow启动时或从后台进入前台显示onHide从前台进入…

Django实战项目-学习任务系统-用户注册

接着上期代码框架&#xff0c;开发第2个功能&#xff0c;用户注册&#xff0c;在原有用户模型基础上&#xff0c;增加一个学生用户属性表&#xff0c;用来关联学生用户的各种属性值&#xff0c;这个属性表是参考网络小说里系统属性值设计的&#xff0c;方便直观了解用户的能力高…

如何使用摩尔信使MThings连接网络设备

帽子&#xff1a; 摩尔信使MThings支持Modbus-TCP、Modbus-RTU Over TCP、Modbus-TCP Over UDP、Modbus-RTU Over UDP。 TCP链接中&#xff0c;摩尔信使MThings支持灵活的连接方式&#xff0c;主机可作为客户端也可以作为服务端&#xff0c;同时支持模拟从机以客户端方式向远…

新媒体达人投放技巧有哪些,投放总结!

达人投放&#xff0c;一个当今时代品牌传播跳不开的词。关于达人投放的优势与特点&#xff0c;相信所有人都已经不在陌生。但是真的进行达人投放时&#xff0c;又该如何实施&#xff0c;今天来分享下新媒体达人投放技巧有哪些&#xff0c;投放总结&#xff01; 一、品牌不同阶段…

C语言,输出最长连号的个数

数据范围&#xff1a;0 < n <10000. 最长连号&#xff0c;就是一组数字里面出现的连续的数字的最长长度。这里的连号最长是2 3 4 5 6&#xff0c;个数为5。 要实现求连号的个数&#xff0c;就要创建一个变量&#xff0c;用来专门计算连号的个数。在不满足连号时&#xf…

【超分】A Benchmark for Chinese-English Scene Text Image Super-resolution

中英文场景文本图像超分辨率的基准 摘要&#xff1a;场景文本图像超分&#xff08;STISR&#xff0c;Scene Text Image Super-resolution&#xff09;就是将低分辨率图像恢复为具有令人愉快的视觉和可读的文本内容。现有工作都是处理笔画简单的英文字符而不是复杂的中文字符。…

安科瑞ARB5系列弧光保护装置,智能电弧光保护,保障用电安全

安科瑞虞佳豪壹捌柒陆壹伍玖玖零玖叁 什么是弧光 电弧是放电过程中发生的一种现象&#xff0c;当两点之间的电压超过其工频绝缘强度极限时就会发生。当适当的条件出现时&#xff0c;一个携带着电流的等离子产生&#xff0c;直到电源侧的保护设备断开才会消失。空气在通常条件…

slamplay:用C++实现的SLAM工具集

0. 项目简介 slamplay 是一个功能强大的工具集合&#xff0c;可用于开始使用 C 来玩和试验 SLAM。这是一项正在进行的工作。它在单个 cmake 框架中安装并提供一些最重要的功能 后端框架&#xff08;g2o、gtsam、ceres、se-sync 等&#xff09;、 前端工具&#xff08;opencv、…

Python教程——配置环境,再探IDE

文章目录 一、Python安装下载安装验证 二、第一个Python程序常见问题 三、Python解释器四、PyCharm工具安装和配置安装使用PyCharm基本使用 一、Python安装 下载 如果我们想要使用Python语言编写程序&#xff0c;我们必须下载Python安装包并配置Python环境&#xff0c;我们现…

Apache Ranger:(一)安装部署

1.Ranger简介 Apache Ranger提供一个集中式安全管理框架, 并解决授权和审计。它可以对Hadoop生态的组件如HDFS、Yarn、Hive、Hbase等进行细粒度的数据访问控制。通过操作Ranger控制台,管理员可以轻松的通过配置策略来控制用户访问权限。 说白了就是管理大多数框架的授权问题。 …

arcgis地形分析全流程

主要内容&#xff1a;DEM的获取与处理、高程分析、坡度分析、坡向分析、地形起伏度分析、地表粗糙度分析、地表曲率分析&#xff1b; 主要工具&#xff1a;镶嵌至新栅格、按掩膜提取、投影栅格、坡度、坡向、焦点统计 一 DEM的获取与处理 1.1 DEM是什么&#xff1f; DEM(D…

ceph版本和Ceph的CSI驱动程序

ceph版本和Ceph的CSI驱动程序 ceph查看ceph版本Ceph的CSI驱动程序 ceph ceph版本和Ceph的CSI驱动程序 查看ceph版本 官网ceph-releases-index Ceph的CSI驱动程序 Ceph的CSI驱动程序 https://github.com/ceph/ceph-csi

F. Vasilije Loves Number Theory

Problem - F - Codeforces 思路&#xff1a;分析一下题意&#xff0c;对于第一种操作来说&#xff0c;每次乘以x&#xff0c;那么nn*x&#xff0c;然后问是否存在一个a使得gcd(n,a)1并且n*a的约数个数等于n&#xff0c;有最大公约数等于1我们能够知道其实这两个数是互质的&…

wireshark抓包分析HTTP协议,HTTP协议执行流程,

「作者主页」&#xff1a;士别三日wyx 「作者简介」&#xff1a;CSDN top100、阿里云博客专家、华为云享专家、网络安全领域优质创作者 「推荐专栏」&#xff1a;对网络安全感兴趣的小伙伴可以关注专栏《网络安全入门到精通》 使用WireShark工具抓取「HTTP协议」的数据包&#…

RedissonClient中Stream流的简单使用

1、pub端 //获取一个流 RStream rStream redissonClient.getStream("testStream"); //创建一个map&#xff0c;添加数据 Map<String, Object> rr new HashMap<>(); rr.put("xx", RandomUtil.randomString(5)); //添加到流 rStream.addAll(r…

Allegro如何查看器件的管脚号?

Allegro在默认情况下,器件是不显示管脚号的。 Allegro默认情况下,器件不显示管脚编号。 在PCB布局时,有时候我们需要看器件的管脚号,然后才能方便布局。那如何查看器件的管脚号呢? 这里介绍两种查看器件的管脚编号的方法。 方法一: (1)选择菜单Display→Color/Visi…

一款好用的PDF文档解密软件

PDF Decrypter pro 纯免费&#xff0c;没有页数限制&#xff0c;没有额外水印&#xff0c;强烈推荐&#xff01;

提升后端API性能的几种解决方案

&#x1f514;目的 提升后端API性能的主要目的是为了提高系统整体的响应速度、并发能力以及可用性。主要原因包括: 提高用户体验 后端API性能好可以减少响应延迟,给用户流畅的体验。 提高系统吞吐量 优化API性能可以提高系统的整体吞吐量,处理更多用户请求。 节省服务器资源…