【学会动态规划】最大子数组和(19)
目录
动态规划怎么学?
1. 题目解析
2. 算法原理
1. 状态表示
2. 状态转移方程
3. 初始化
4. 填表顺序
5. 返回值
3. 代码编写
写在最后:
动态规划怎么学?
学习一个算法没有捷径,更何况是学习动态规划,
跟我一起刷动态规划算法题,一起学会动态规划!
1. 题目解析
题目链接:53. 最大子数组和 - 力扣(LeetCode)

题目很好理解,顾名思义,就是找最大的子数组和。
2. 算法原理
1. 状态表示
dp [ i ] 位置表示以 i 位置元素为结尾的所有子数组的最大和。
2. 状态转移方程
状态转移方程有两种情况,
1. 子数组长度为 1 时,最大和就是 i 位置的值
2. 子数组长度大于 1 是,最大和就是上一个位置的最大和 + 当前位置的值
所以我们就可以得出状态转移方程
dp [ i ] = max( nums[ i ],dp[ i ] + nums[ i ] )
3. 初始化
初始化就是防止越界,并且不影响后面的值,
初始化成 0 即可。
4. 填表顺序
从左往右即可。
5. 返回值
返回整个 dp 表里的最大值。
3. 代码编写
class Solution {
public:int maxSubArray(vector<int>& nums) {int n = nums.size();vector<int> dp(n + 1);int ans = INT_MIN;for(int i = 1; i <= n ; i++) {dp[i] = max(nums[i - 1], dp[i - 1] + nums[i - 1]);ans = max(ans, dp[i]);}return ans;}
};
写在最后:
以上就是本篇文章的内容了,感谢你的阅读。
如果感到有所收获的话可以给博主点一个赞哦。
如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~
相关文章:
【学会动态规划】最大子数组和(19)
目录 动态规划怎么学? 1. 题目解析 2. 算法原理 1. 状态表示 2. 状态转移方程 3. 初始化 4. 填表顺序 5. 返回值 3. 代码编写 写在最后: 动态规划怎么学? 学习一个算法没有捷径,更何况是学习动态规划, 跟我…...
怎么做Tik Tok海外娱乐公会呢?新加坡市场怎么样?
一、为什么选择TikTok直播 1. 海外市场潜力巨大 • 自2016年始,多家直播平台陆续拓展至东南亚、中东、俄罗斯、日韩、欧美、拉美等地区。 • 海外市场作为直播发展新蓝海,2021年直播行业整申请cmxyci体规模达百亿美元,并维持高速增长。 &a…...
mysql主从复制搭建
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言MySQL复制过程分为三部: 一、准备工作二、配置>主库Master三、配置>从库SlaveSlave_IO_Running: YesSlave_SQL_Running: Yes 四、测试至此&am…...
Java:正则表达式案例:爬数据,重复数据替换,数据分割
使用正则表达式查找一段文本中的内容 需求:请把下面文本中的电话,邮箱,座机号码,热线都爬取出来。 String data "电话:1866668888,18699997777\n" "或者联系邮箱: boniuitcast.cn,\n" "座机…...
CF 765D Artsem and Saunders 构造
CF765D Artsem and Saunders 直接猜一种构造做法, h ( x ) h(x) h(x)的值域一定和 f ( x ) f(x) f(x)的值域一样,我们先满足 h ( g ( x ) ) f ( x ) h(g(x))f(x) h(g(x))f(x)这个条件,遍历 f ( x ) f(x) f(x),每次添加 h ( x ) h…...
DevOps系列文章 之 SpringBoot整合GitLab-CI实现持续集成
在企业开发过程中,我们开发的功能或者是修复的BUG都需要部署到服务器上去,而这部分部署操作又是重复且繁琐的工作,GitLab-CI 持续集成为我们解决了这一痛点,将重复部署的工作自动化,大大的节省了程序员们的宝贵时间。本…...
K8S系列二:实战入门
I. 配置kubectl 1.1 什么是kubectl? 官方文档中介绍kubectl是: Kubectl 是一个命令行接口,用于对 Kubernetes 集群运行命令。Kubectl的配置文件在$HOME/.kube目录。我们可以通过设置KUBECONFIG环境变量或设置命令参数–kubeconfig来指定其他…...
form中表单切换,导致 relus 中的事件无法触发,原因:页面切换不要一直切换DOM,会导致问题,需要都显示出来
修改前,因为重复渲染DOM导致绑定rules失效 修改前代码使用 computed 计算出渲染的DOM,影响rules事件<el-formref"form"inline:model"billDetailCopy":rules"rules"size"small"label-position"right&quo…...
Android Ble蓝牙App(五)数据操作
Ble蓝牙App(五)数据操作 前言正文一、操作内容处理二、读取数据① 概念② 实操 三、写入数据① 概念② 实操 四、打开通知一、概念二、实操三、收到数据 五、源码 前言 关于低功耗蓝牙的服务、特性、属性、描述符都已经讲清楚了,而下面就是使…...
.netcore grpc双向流方法详解
一、双向流处理概述 简单来讲客户端可以向服务端发送消息流,服务端也可以向客户端传输响应流,即客户端和服务端可以互相通讯客户端无需发送消息即可开始双向流式处理调用 。 客户端可选择使用 RequestStream.WriteAsync 发送消息。 使用 ResponseStream…...
【Servlet】(Servlet API HttpServlet 处理请求 HttpServletRequest 打印请求信息 前端给后端传参)
文章目录 Servlet APIHttpServlet处理请求 HttpServletRequest打印请求信息前端给后端传参 Servlet API Servlet中常用的API HttpServlet 实际开发的时候主要重写 doXXX 方法, 很少会重写 init / destory / service destory 服务器终止的时候会调用. //下面的注解把当前类和…...
java中右移>>和无符号右移>>>的区别
public static void main(String[] args) {byte[] dest new byte[2];dest[0] 0x15; //0001 0101dest[1] (byte) 0xfb;//1111 1011System.out.println((dest[0] >> 4) & 0xff);//右移 应该是0000 0001 十进制结果显示1 结果也是1,正确System.out.printl…...
牛客周赛 Round 7
目录 A 游游的you矩阵 题目: 题解: AC 代码: B 游游的01串操作 题目: 题解: AC 代码: C 游游的正整数 题目: 题解: AC 代码: D 游游的选数乘积 题目…...
R语言生存分析(机器学习)(1)——GBM(梯度提升机)
GBM是一种集成学习算法,它结合了多个弱学习器(通常是决策树)来构建一个强大的预测模型。GBM使用“Boosting”的技术来训练弱学习器,这种技术是一个迭代的过程,每一轮都会关注之前轮次中预测效果较差的样本,…...
k8s和docker简单介绍
当涉及到容器技术和容器编排时,Docker和Kubernetes是两个重要的概念。我将更详细地介绍它们以及它们之间的关系。 Docker: Docker是一种容器化技术,它允许你将应用程序及其依赖项打包到一个称为"容器"的封闭环境中。每个容器都包…...
Lua学习记录
Lua基础了解 Lua的注释通过 (-- 单行注释,--[[ ]] 多行注释)可以不加; 多个变量赋值,按顺序赋值,没有则为nil; function的简单用法,多个返回值配合多重赋值,以end为结束标志 Lua下标从1开始&…...
三分钟完美解决你的C盘内存过大爆红
一、清理回收站 二、清理桌面 建议一 不要在桌面放太多图标或者文件会占用过多的内存,可以放到其他盘建议二、 将位置移动到别的盘 三、手动删除下载文件与缓存文件 日常使用中会通过Windows下载各种文件资料到电脑中,它默认也是直接下载在C盘中的。如果我们在以…...
C++ - equal(比较两个vector元素)
C标准库的std::equal函数。这个函数用于比较两个范围的元素是否相等。 在使用std::equal函数时,您需要提供两个范围的迭代器,以及一个可选的谓词函数(predicate)。函数会比较第一个范围内的元素和第二个范围内的元素是否相等。如果…...
多线程:线程池
线程池 提前创建多个线程放入线程池中,使用时直接获取,使用完直接放入池中;可以避免频繁创建销毁,实现重复利用,类似生活中的公共交通工具。好处:提高相应速度;降低资源消耗;便于线…...
9.3.2.2网络原理(传输层TCP)
TCP全部细节参考RFC标准文档 一.TCP特点: 有连接,可靠传输,面向字节流,全双工. 二.TCP数据报: 1.端口号是传输层的重要概念. 2.TCP的报头是变长的(UDP是固定的8字节),大小存在4位首部长度中,用4个bit位(0~15)表示长度单位是4字节.(TCP报头最大长度是60字节,前面20字节是固定…...
(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...
ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放
简介 前面两期文章我们介绍了I2S的读取和写入,一个是通过INMP441麦克风模块采集音频,一个是通过PCM5102A模块播放音频,那如果我们将两者结合起来,将麦克风采集到的音频通过PCM5102A播放,是不是就可以做一个扩音器了呢…...
【论文阅读28】-CNN-BiLSTM-Attention-(2024)
本文把滑坡位移序列拆开、筛优质因子,再用 CNN-BiLSTM-Attention 来动态预测每个子序列,最后重构出总位移,预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵(S…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...
以光量子为例,详解量子获取方式
光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学(silicon photonics)的光波导(optical waveguide)芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中,光既是波又是粒子。光子本…...
【C++进阶篇】智能指针
C内存管理终极指南:智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...
tomcat指定使用的jdk版本
说明 有时候需要对tomcat配置指定的jdk版本号,此时,我们可以通过以下方式进行配置 设置方式 找到tomcat的bin目录中的setclasspath.bat。如果是linux系统则是setclasspath.sh set JAVA_HOMEC:\Program Files\Java\jdk8 set JRE_HOMEC:\Program Files…...
十九、【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建
【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建 前言准备工作第一部分:回顾 Django 内置的 `User` 模型第二部分:设计并创建 `Role` 和 `UserProfile` 模型第三部分:创建 Serializers第四部分:创建 ViewSets第五部分:注册 API 路由第六部分:后端初步测…...
深度解析云存储:概念、架构与应用实践
在数据爆炸式增长的时代,传统本地存储因容量限制、管理复杂等问题,已难以满足企业和个人的需求。云存储凭借灵活扩展、便捷访问等特性,成为数据存储领域的主流解决方案。从个人照片备份到企业核心数据管理,云存储正重塑数据存储与…...
Qt Quick Controls模块功能及架构
Qt Quick Controls是Qt Quick的一个附加模块,提供了一套用于构建完整用户界面的UI控件。在Qt 6.0中,这个模块经历了重大重构和改进。 一、主要功能和特点 1. 架构重构 完全重写了底层架构,与Qt Quick更紧密集成 移除了对Qt Widgets的依赖&…...
