动态规划 —— 子数组系列-最大子数组和

1. 最大子数组和

题目链接:

53. 最大子数组和 - 力扣(LeetCode)icon-default.png?t=O83Ahttps://leetcode.cn/problems/maximum-subarray/description/

 


2. 算法原理

状态表示:以某一个位置为结尾或者以某一个位置为起点

  

dp[i]表示:以i位置为结尾的所有子树中的最大和

2. 状态转移方程

  

dp[i]分为两种情况:1. 长度为1        nums[i]

  

                                 2. 长度大于1        dp[i-1] + nums[i]

  

本题的状态转移方程为:max(nums[i] ,  dp[i-1] + nums[i])

  

3. 初始化 :把dp表填满不越界,让后面的填表可以顺利进行

  

我们可以在左边加上一个虚拟节点,为了不影响最终结果,那么就可以把这个虚拟节点初始化为0

  

本题的下标映射关系:往后一点一位就行了

  

4. 填表顺序 

  

本题的填表顺序是:从左往右

5. 返回值 :题目要求 + 状态表示     

  

本题的返回值是:整个dp表里的最大值


3.  代码 

  动态规划的固定四步骤:1.  创建一个dp表

                                        2. 在填表之前初始化

                                        3. 填表(填表方法:状态转移方程)

                                        4. 确定返回值

class Solution {
public:int maxSubArray(vector<int>& nums) {int n=nums.size();vector<int>dp(n+1);int ret=INT_MIN;//定义一个最小值与数组里比较for(int i=1;i<=n;i++){dp[i]=max(nums[i-1],dp[i-1]+nums[i-1]);ret=max(ret,dp[i]);}return ret;}
};


未完待续~

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

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

相关文章

【教程】华南理工大学国际校区宿舍门锁声音设置

转载请注明出处&#xff1a;小锋学长生活大爆炸[xfxuezhagn.cn] 如果本文帮助到了你&#xff0c;欢迎[点赞、收藏、关注]哦~ 视频教程&#xff1a;【教程】华南理工大学国际校区宿舍门锁声音设置_哔哩哔哩_bilibili 来自&#xff1a; https://tieba.baidu.com/p/8297840035

【AI技术对电商的影响】

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…

uni-app中使用 unicloud 云开发平台③

文章目录 六、hbuilderX 中使用 unicloud 云开发平台文档传统业务开发流程什么是 unicloudunicloud 优点开发流程uncloud 构成云数据库云存储及 CDN创建云函数工程七、unicloud api 操作云函数调用云函数实现云数据库基本增删改查1. 获取数据库引用云存储操作六、hbuilderX 中使…

智享AI 无人自动直播的崛起 ,引领智能互动与自动带货新潮流!

在当今数字化飞速发展的时代&#xff0c;商业领域正经历着一场前所未有的变革。智能互动与自动带货成为了新的潮流&#xff0c;而其中最引人瞩目的便是最新的 AI 无人自动直播玩法&#xff0c;它宛如一股强劲的东风&#xff0c;引领着行业的风向。 AI 无人自动直播是多种先进技…

科技云报到:数字化转型,从不确定性到确定性的关键路径

科技云报到原创。 数字化转型是VUCA时代最大的确定性。 如果说&#xff0c;过去是数字化转型的试验阶段&#xff0c;实施的是开荒动土、选种育苗&#xff0c;那么当前要进行的是精耕细作、植树造林&#xff0c;数字化转型已进入了由个别行业、个别场景的“点状应用”向各行各业…

vue3+vite 前端打包不缓存配置

最近遇到前端部署后浏览器得清缓存才能出现最新页面效果得问题 所以…按以下方式配置完打包就没啥问题了&#xff0c;原理很简单就是加个时间戳 /* eslint-disable no-undef */ import {defineConfig, loadEnv} from vite import path from path import createVitePlugins from…

基于Qt/C++全局键盘和鼠标事件监控工具

项目介绍&#xff1a; 该项目实现了一个基于 Qt 框架的全局键盘和鼠标事件监控工具&#xff0c;主要功能包括&#xff1a; 实时监控全局键盘事件&#xff1a;捕获并显示所有键盘按键&#xff0c;并将按键的虚拟键码转为键名显示。实时监控全局鼠标事件&#xff1a;捕获并显示…

华为数通HCIA系列第5次考试-【2024-46周-周一】

文章目录 1、子网掩码有什么作用&#xff0c;和IP地址是什么关系&#xff0c;利用子网掩码可以获取哪些信息&#xff1f;2、已知一个IP地址是192.168.1.1&#xff0c;子网掩码是255.255.255.0&#xff0c;求其网络地址3、已知某主机的IP地址是192.168.100.200&#xff0c;子网掩…

arkUI:遍历数据数组动态渲染(forEach)

arkUI&#xff1a;遍历数据数组动态渲染&#xff08;forEach&#xff09; 1 主要内容说明2 相关内容2.1 ForEach 的基本语法2.2 简单遍历数组2.2 多维数组遍历2.4 使用唯一键2.5 源码1的相关说明2.5.1 源码1 &#xff08;遍历数据数组动态渲染&#xff09;2.5.2 源码1运行效果 …

Ue5 umg学习(一)

学习视频资料链接 2、UI编辑界面_哔哩哔哩_bilibili 打开ue5虚幻引擎 创建新的文件夹UI&#xff0c;在这个文件夹里写东西 点击停靠在布局中 双击点进UI文件夹 右键用户界面&#xff0c;选择控件蓝图 创建控件蓝图&#xff0c;重命名&#xff0c;在名称后面加一个_BP1代表是…

PYNQ 框架 - 中断(INTR)驱动

目录 1. 简介 2. 分析 2.1 Block Design 2.2 AXI Timer 2.2.1 IP 基本信息 2.2.2 IP 地址空间 2.2.3 级联模式 2.2.4 生成/捕获模式 2.3 AXI Interrupt 2.3.1 IP 基本信息 2.3.2 IP 地址空间 2.3.3 相关概念 2.3.4 参数配置 2.3.5 中断确认寄存器 3. PYNQ 代码 …

RAG综述:《A Comprehensive Survey of Retrieval-Augmented Generation (RAG)》

来源于《A Comprehensive Survey of Retrieval-Augmented Generation (RAG): Evolution, Current Landscape and Future Directions》 一、RAG所解决的问题 如何有效地从外部知识源检索相关信息&#xff0c;如何将这些信息无缝地融入到生成文本中&#xff0c;以及如何在保证生…

GitLab 如何跨版本升级?

本分分享 GitLab 跨版本升级的一些注意事项。 众所周知&#xff0c;GitLab 的升级必须要严格遵循升级路径&#xff0c;否则就会出现问题&#xff0c;导致升级失败。因此&#xff0c;在 GitLab 升级之前需要做好两件事情&#xff1a; 当前版本的确认升级路径的确认 极狐GitLa…

aws(学习笔记第十二课) 使用AWS的RDS-MySQL

aws(学习笔记第十二课) 使用AWS的RDS 学习内容&#xff1a; AWS的RDS-MySQL 1. 使用AWS的RDS 什么是RDS RDS就是Relation Database Service的缩写&#xff0c;是AWS提供的托管关系型数据库系统。让用户能够在 AWS Cloud 云中更轻松地设置、操作和扩展关系数据库。 数据库和we…

云原生-docker安装与基础操作

一、云原生 Docker 介绍 Docker 在云原生中的优势 二、docker的安装 三、docker的基础命令 1. docker pull&#xff08;拉取镜像&#xff09; 2. docker images&#xff08;查看本地镜像&#xff09; 3. docker run&#xff08;创建并启动容器&#xff09; 4. docker ps…

Spark 核心概念与宽窄依赖的详细解析

Spark 的介绍与搭建&#xff1a;从理论到实践_spark环境搭建-CSDN博客 Spark 的Standalone集群环境安装与测试-CSDN博客 PySpark 本地开发环境搭建与实践-CSDN博客 Spark 程序开发与提交&#xff1a;本地与集群模式全解析-CSDN博客 Spark on YARN&#xff1a;Spark集群模式…

【css】html里面的图片宽度设为百分比,高度要与宽度一样

场景&#xff1a;展示图片列表的时候&#xff0c;原始图片宽高不一致。 外层div的宽度自适应&#xff0c;图片宽度不能固定数值&#xff0c;只能设置百分比。图片高度也不能设置固定数值。 如何让图片的高度与图片的宽度一样呢&#xff1f; html代码 &#xff1a; <div cl…

c#使用COM接口设置excel单元格宽高匹配图片,如何计算?

c#使用COM接口设置excel单元格宽高如何换算 在实际工作中&#xff0c;经常需要在excel中插入图片。并设置单元格与图片对齐。但是excel单元格的宽度和高度使用不同的单位。单元格的宽度以字符宽度为单位&#xff0c;而高度以点为单位。如果按照实际值来设置&#xff0c;例如设…

RHCE web解析、dns配置、firewalld配置实验

RHCE web解析、dns配置、firewalld配置实验 实验一1.清理软件包2.安装软件包3.配置web服务查看默认测试页面报错讲解12 4.安装DNS解析需要的bind软件包5.修改网络配置&#xff0c;查错&#xff0c;修改权限 实验二配置文件haha.confnamed.confnamed.haha 实验一 1、学习方法 重…

JavaEE进阶----SpringMVC(三)---响应的获取

文章目录 1.cookie和session获取1.1servlet写法获取1.2spring获取cookie1.3传统方法获取session1.4sring获取session内容 2.访问静态页面3.一个项目部署多个服务4.responsebody的介绍5.返回html的片段6.不同相应content-type类型6.1text/html类型6.2application-json类型6.3 js…