算法系列--动态规划--⼦数组、⼦串系列(数组中连续的⼀段)(1)
💕"我们好像在池塘的水底,从一个月亮走向另一个月亮。"💕
作者:Mylvzi
文章主要内容:算法系列–动态规划–⼦数组、⼦串系列(数组中连续的⼀段)(1)
大家好,今天为大家带来的是
算法系列--动态规划--⼦数组、⼦串系列(数组中连续的⼀段)(1)
,这是动态规划新的一种题型
1.最⼤⼦数组和
链接:
https://leetcode.cn/problems/maximum-subarray/
分析:
动态规划的子数组问题和前缀和问题是不一样的
,
子数组和这道题要求的是子数组和的最大值,我们的状态表示就是记录以i位置为结束的所有子数组的最大和,而前缀和只是一种快速求出区间和的方法,并没有表示最大和这种状态
关于求最大子数组和问题这道题,要注意状态表示的含义以i位置为结尾的所有子数组的最大和
,也就是必须以i位置为结尾
,那么此时的状态其实只有两种:
- 单独一个
- 前面的一堆 + 它本身
网上的很多推到状态方程的时候其实很容易让人误解,解释的也不清楚,他们进行状态的分类是根据dp[i - 1]的正负来推导dp[i]的,有的人可能想为什么不判断nums[i]的正负呢?
其实本质都一样,笔者觉得单纯通过形式
来推到方程更容易理解一些
子串/子数组问题的一个经验的状态分类就是按照长度
分类的,因为他们的状态表示都比较固定,都是以i位置为结束的最大xxxx
有的题目还比较恶心(尤其是关于子串的问题),对于相同的子串有时候还需要去重,就需要额外开一个数组来统计次数
本题的分析思路:
代码:
class Solution {public int maxSubArray(int[] nums) {int n = nums.length;int dp = 0;int max = -0x3f3f3f3f;// 将最大/小值设置为+-ox3f3f3f3f是一种经验for(int num : nums) {dp = Math.max(num,dp + num);// 填表max = Math.max(max,dp);// 更新最值}return max;}
}
2.环形⼦数组的最⼤和
链接:
https://leetcode.cn/problems/maximum-sum-circular-subarray/description/
分析:
本题是上题的一个变种
,这里带环了,对于带环的问题,我们最常用的一个做法是想办法将其转化为线性的
,对于本题我们可以采用分类讨论的思想
根据什么区分类讨论呢?往往是根据最后结果可能出现的形式
去考虑,对于本题,最长的子数组和可能是两种情况
- 不带环,在区间内部
- 带环,跨越区间
对于情况1
,就是最大子数组和
的解法,对于情况2
,可以转化为求区间内的最小值,那么最大值就是sum - min
,最后返回情况1和情况2的最大值即可
下面是详细分析过程
代码:
class Solution {public int maxSubarraySumCircular(int[] nums) {// 创建dp表int n = nums.length;if(n == 1) return nums[0];int[] f = new int[n];int[] g = new int[n];// 初始化f[0] = g[0] = nums[0];int max = -0x3f3f3f3f;int min = 0x3f3f3f3f;int sum = nums[0];// 填表for(int i = 1; i < n; i++) {f[i] = Math.max(nums[i],f[i - 1] + nums[i]);g[i] = Math.min(nums[i],g[i - 1] + nums[i]);max = Math.max(max,f[i]);min = Math.min(min,g[i]);sum += nums[i];}// 返回值return sum == min ? max : Math.max(max,sum - min);}
}
3.乘积最⼤⼦数组
链接:
https://leetcode.cn/problems/maximum-product-subarray/
分析:
首先想到的状态表示就是以i位置为结尾子数组的最大乘积
,但是根据这个状态表示去推到状态转移方程时发现只使用一个dp表无法表示所有的情况
- 当
nums[i] > 0
,i位置的状态就是前一个位置的最大乘积 * nums[i] - 当
nums[i] < 0
,此时无法通过dp[i - 1]来推到dp[i],因为一个负数 * 较大的数一定会变小,那么dp[i]存储的就是以i位置为结尾的子数组的最小乘积
,这与我们的状态表示是矛盾的
既然当nums[i] < 0
时,需要乘的是以i-1位置为结尾的子数组的最小乘积
,那么我们就创建出一个dp表g[i]
来表示最小乘积,以下是详细分析过程:
代码:
class Solution {public int maxProduct(int[] nums) {// 创建dp表int n = nums.length;int[] f = new int[n];int[] g = new int[n];// 初始化f[0] = g[0] = nums[0];int max = f[0];// 填表for(int i = 1; i < n; i++) {int t1 = 0, t2 = 0;if(nums[i] > 0) {f[i] = f[i - 1] * nums[i];g[i] = g[i - 1] * nums[i];}else {f[i] = g[i - 1] * nums[i];g[i] = f[i - 1] * nums[i];}f[i] = Math.max(nums[i],f[i]);g[i] = Math.min(nums[i],g[i]);max = Math.max(f[i],max);}return max;}
}
4.乘积为正数的最⻓⼦数组
链接:
https://leetcode.cn/problems/maximum-length-of-subarray-with-positive-product/description/
分析:
本题相较于上题有两个不同:
- 本题要求乘积必须为正数
- 本题求解的不是最大的乘积,而是乘积为正数的最长子数组
和上题一样,本题同样需要使用两个dp表来进行状态表示
f[i]
:以i位置为结尾,乘积为正数的最大子数组长度g[i]
:以i位置为结尾,乘积为负数的最大子数组长度
状态转移方程推导如下:
注意特殊情况:
- 当n[i] < 0时,
f[i] == g[i - 1] + 1
,但是如果i位置之前全是正数,此时g[i - 1] == 0
,那么f[i] == 0 + 1 = 1了,但是因为n[i] < 0,i位置的f[i]应该等于 0,因为所有的以i位置为结尾的子数组的乘积必然为负数
代码:
class Solution {public int getMaxLen(int[] nums) {int n = nums.length;// 1.创建dp表int[] f = new int[n];int[] g = new int[n];// 2.根据状态表示进行初始化f[0] = nums[0] > 0 ? 1 : 0;g[0] = nums[0] < 0 ? 1 : 0;int max = -0x3f3f3f3f;// 3.填表for(int i = 1; i < n; i++) {if(nums[i] > 0) {f[i] = f[i - 1] + 1;g[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;}else if(nums[i] < 0){f[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;g[i] = f[i - 1] + 1;}else {f[i] = g[i] = 0;// 注意等于0相当于直接截断 要重新计数 从0开始}max = Math.max(f[i],max);// 更新长度}// 处理n == 1的情况return max == -0x3f3f3f3f ? f[0] : max;}
}
总结
:
- 子数组问题最常用的一种状态表示就是
以i位置为结尾的xxxx
- 在推导状态转移方程时,往往是根据
组成子数组的形态
来分类讨论(单独一个还是和前面一堆组成子数组)
相关文章:

算法系列--动态规划--⼦数组、⼦串系列(数组中连续的⼀段)(1)
💕"我们好像在池塘的水底,从一个月亮走向另一个月亮。"💕 作者:Mylvzi 文章主要内容:算法系列–动态规划–⼦数组、⼦串系列(数组中连续的⼀段)(1) 大家好,今天为大家带来的是算法系…...
RESTful架构
RESTful架构中的URI设计与传统的URL设计有一些区别。让我通过具体的例子来解释一下: 传统的URL设计通常将操作和资源混合在一起,例如: 获取所有图书:GET /getBooks获取特定图书:GET /getBookById/{id}创建新图书&…...

从IO操作与多线程的思考到Redis-6.0
IO操作->线程阻塞->释放CPU资源->多线程技术提升CPU利用率 在没有涉及磁盘操作和网络请求的程序中,通常不会出现线程等待状态。线程等待状态通常是由于线程需要等待某些事件的发生,比如I/O操作完成、网络请求返回等。如果程序只是进行计算或者简…...
MNN介绍、安装和编译
MNN是一个轻量级的深度学习推理框架,由阿里巴巴公司开发。它支持多种硬件平台,包括CPU、GPU和NPU,并提供高效、高性能的深度学习模型推理服务。下面是MNN的安装和编译步骤: 下载MNN源代码 在MNN的GitHub页面(https://g…...

【计算机图形学】AO-Grasp: Articulated Object Grasp Generation
对AO-Grasp: Articulated Object Grasp Generation的简单理解 文章目录 1. 做的事情2. AO-Grasp数据集2.1 抓取参数化和label标准2.2 语义和几何感知的抓取采样 3. AO-Grasp抓取预测3.1 预测抓取点3.2 抓取方向预测 4. 总结 1. 做的事情 引入AO-Grasp,grasp propo…...

「媒体宣传」财经类媒体邀约资源有哪些?-51媒体
传媒如春雨,润物细无声,大家好,我是51媒体网胡老师。 财经类媒体邀约资源包括但不限于以下几类: 商业杂志和报纸:可以邀请如《财经》、《新财富》、《经济观察报》等主流商业杂志和报纸。这些媒体通常具有较强的品牌影…...
学习资料记录
http://interview.wzcu.com/Golang/%E4%BB%A3%E7%A0%81%E8%80%83%E9%A2%98.html map底层 https://zhuanlan.zhihu.com/p/616979764 go修养 https://www.yuque.com/aceld/golang/ga6pb1#4b19dba5 https://golang.dbwu.tech/performance/map_pre_alloc/ https://juejin.cn/pos…...

数据结构进阶篇 之 【二叉树】详细概念讲解(带你认识何为二叉树及其性质)
有朋自远方来,必先苦其心志,劳其筋骨,饿其体肤,空乏其身,鞭数十,驱之别院 一、二叉树 1、二叉树的概念 1.1 二叉树中组分构成名词概念 1.2 二叉树的结构概念 1.3 特殊的二叉树 2、二叉树的存储结构 …...

vue.js制作学习计划表案例
通俗易懂,完成“学习计划表”用于对学习计划进行管理,包括对学习计划进行添加、删除、修改等操作。 一. 初始页面效果展示 二.添加学习计划页面效果展示 三.修改学习计划完成状态的页面效果展示 四.删除学习计划 当学习计划处于“已完成”状态时&…...
nginx localtion 匹配规则
1、语法规则 语法规则:location[|~|^~*|^~]/uri/{… } 表示精确匹配,这个优先级也是最高的 ^~ 表示 uri 以某个常规字符串开头,理解为匹配 url 路径即可。 nginx 不对 url 做编码,因此请求为 /image/20%/aa,可以被规则^~ /imag…...
Git:分布式版本控制系统
目录 Git的特点和功能常见的功能和对应的命令 Git的特点和功能 Git是一个分布式版本控制系统,用于跟踪和管理项目的代码变更。它是由Linus Torvalds在2005年创建的,旨在管理Linux内核的开发。Git具有以下特点和功能: 分布式版本控制…...

[STL]priority_queue类及反向迭代器的模拟实现
🪐🪐🪐欢迎来到程序员餐厅💫💫💫 今日主菜: priority_queue类及反向迭代器 主厨:邪王真眼 主厨的主页:Chef‘s blog 所属专栏:c大冒险 向着c&…...

vue2 脚手架
安装 文档:https://cli.vuejs.org/zh/ 第一步:全局安装(仅第一次执行) npm install -g vue/cli 或 yarn global add vue/cli 备注:如果出现下载缓慢:请配置npm 淘宝镜像: npm config set regis…...
【OpenStack】OpenStack实战之开篇
目录 那么,OpenStack是什么?云又是什么?关于容器应用程序OpenStack如何适配其中?如何设置它?如何学会使用它?推荐超级课程: Docker快速入门到精通Kubernetes入门到大师通关课AWS云服务快速入门实战我的整个职业生涯到目前为止一直围绕着为离线或隔离网络设计和开发应用程…...
Python实现WebSocket通信
WebSocket是一种在单个TCP连接上进行全双工通信的协议,位于 OSI 模型的应用层。 与传统的HTTP请求-响应模型不同,WebSocket的最大特点就是,服务器可以主动向客户端推送信息,客户端也可以主动向服务器发送信息,实现实时性和互动性…...

MATLAB 自定义生成直线点云(详细介绍) (47)
MATLAB 自定义生成直线点云 (详细介绍)(47) 一、算法介绍二、具体步骤二、算法实现1.代码2.效果一、算法介绍 通过这里的直线生成方法,可以生成模拟直线的点云数据,并通过调整起点、终点、数量和噪声水平等参数来探索不同类型的直线数据。这种方法可以用于测试、验证和开…...

UniTask 异步任务
文章目录 前言一、UniTask是什么?二、使用步骤三、常用的UniTask API和示例1.编写异步方法2.处理异常3.延迟执行4.等待多个UniTask或者一个UniTas完成5.异步加载资源示例6.手动控制UniTask的完成状态7.UniTask.Lazy延迟任务的创建8.后台线程切换Unity主线程9.不要返…...

【git分支管理策略】如何高效的管理好代码版本
目录 1.分支管理策略 2.我用的分支管理策略 3.一些常见问题 1.分支管理策略 分支管理策略就是一些经过实践后总结出来的可靠的分支管理的办法,让分支之间能科学合理、高效的进行协作,帮助我们在整个开发流程中合理的管理好代码版本。 目前有两套Git…...
css的transition详解
CSS的transition属性是一个简写属性,用于设置四个过渡效果属性,以在元素的状态改变时创建平滑的动画效果。这四个属性分别是: transition-property: 定义应用过渡效果的CSS属性名称。当指定的CSS属性改变时,过渡效果将…...

agent利用知识来做规划:《KnowAgent: Knowledge-Augmented Planning for LLM-Based Agents》笔记
文章目录 简介KnowAgent思路准备知识Action Knowledge的定义Planning Path Generation with Action KnowledgePlanning Path Refinement via Knowledgeable Self-LearningKnowAgent的实验结果 总结参考资料 简介 《KnowAgent: Knowledge-Augmented Planning for LLM-Based Age…...
synchronized 学习
学习源: https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖,也要考虑性能问题(场景) 2.常见面试问题: sync出…...
前端倒计时误差!
提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...

3.3.1_1 检错编码(奇偶校验码)
从这节课开始,我们会探讨数据链路层的差错控制功能,差错控制功能的主要目标是要发现并且解决一个帧内部的位错误,我们需要使用特殊的编码技术去发现帧内部的位错误,当我们发现位错误之后,通常来说有两种解决方案。第一…...

Day131 | 灵神 | 回溯算法 | 子集型 子集
Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣(LeetCode) 思路: 笔者写过很多次这道题了,不想写题解了,大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...
Qt Widget类解析与代码注释
#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码,写上注释 当然可以!这段代码是 Qt …...

【网络安全产品大调研系列】2. 体验漏洞扫描
前言 2023 年漏洞扫描服务市场规模预计为 3.06(十亿美元)。漏洞扫描服务市场行业预计将从 2024 年的 3.48(十亿美元)增长到 2032 年的 9.54(十亿美元)。预测期内漏洞扫描服务市场 CAGR(增长率&…...

linux arm系统烧录
1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 (忘了有没有这步了 估计有) 刷机程序 和 镜像 就不提供了。要刷的时…...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

佰力博科技与您探讨热释电测量的几种方法
热释电的测量主要涉及热释电系数的测定,这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中,积分电荷法最为常用,其原理是通过测量在电容器上积累的热释电电荷,从而确定热释电系数…...

C/C++ 中附加包含目录、附加库目录与附加依赖项详解
在 C/C 编程的编译和链接过程中,附加包含目录、附加库目录和附加依赖项是三个至关重要的设置,它们相互配合,确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中,这些概念容易让人混淆,但深入理解它们的作用和联…...