当前位置: 首页 > news >正文

【学会动态规划】最大子数组和(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)

目录 动态规划怎么学&#xff1f; 1. 题目解析 2. 算法原理 1. 状态表示 2. 状态转移方程 3. 初始化 4. 填表顺序 5. 返回值 3. 代码编写 写在最后&#xff1a; 动态规划怎么学&#xff1f; 学习一个算法没有捷径&#xff0c;更何况是学习动态规划&#xff0c; 跟我…...

怎么做Tik Tok海外娱乐公会呢?新加坡市场怎么样?

一、为什么选择TikTok直播 1. 海外市场潜力巨大 • 自2016年始&#xff0c;多家直播平台陆续拓展至东南亚、中东、俄罗斯、日韩、欧美、拉美等地区。 • 海外市场作为直播发展新蓝海&#xff0c;2021年直播行业整申请cmxyci体规模达百亿美元&#xff0c;并维持高速增长。 &a…...

mysql主从复制搭建

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言MySQL复制过程分为三部&#xff1a; 一、准备工作二、配置>主库Master三、配置>从库SlaveSlave_IO_Running: YesSlave_SQL_Running: Yes 四、测试至此&am…...

Java:正则表达式案例:爬数据,重复数据替换,数据分割

使用正则表达式查找一段文本中的内容 需求:请把下面文本中的电话&#xff0c;邮箱&#xff0c;座机号码&#xff0c;热线都爬取出来。 String data "电话:1866668888&#xff0c;18699997777\n" "或者联系邮箱: boniuitcast.cn&#xff0c;\n" "座机…...

CF 765D Artsem and Saunders 构造

CF765D Artsem and Saunders 直接猜一种构造做法&#xff0c; h ( x ) h(x) h(x)的值域一定和 f ( x ) f(x) f(x)的值域一样&#xff0c;我们先满足 h ( g ( x ) ) f ( x ) h(g(x))f(x) h(g(x))f(x)这个条件&#xff0c;遍历 f ( x ) f(x) f(x)&#xff0c;每次添加 h ( x ) h…...

DevOps系列文章 之 SpringBoot整合GitLab-CI实现持续集成

在企业开发过程中&#xff0c;我们开发的功能或者是修复的BUG都需要部署到服务器上去&#xff0c;而这部分部署操作又是重复且繁琐的工作&#xff0c;GitLab-CI 持续集成为我们解决了这一痛点&#xff0c;将重复部署的工作自动化&#xff0c;大大的节省了程序员们的宝贵时间。本…...

K8S系列二:实战入门

I. 配置kubectl 1.1 什么是kubectl&#xff1f; 官方文档中介绍kubectl是&#xff1a; Kubectl 是一个命令行接口&#xff0c;用于对 Kubernetes 集群运行命令。Kubectl的配置文件在$HOME/.kube目录。我们可以通过设置KUBECONFIG环境变量或设置命令参数–kubeconfig来指定其他…...

form中表单切换,导致 relus 中的事件无法触发,原因:页面切换不要一直切换DOM,会导致问题,需要都显示出来

修改前&#xff0c;因为重复渲染DOM导致绑定rules失效 修改前代码使用 computed 计算出渲染的DOM&#xff0c;影响rules事件<el-formref"form"inline:model"billDetailCopy":rules"rules"size"small"label-position"right&quo…...

Android Ble蓝牙App(五)数据操作

Ble蓝牙App&#xff08;五&#xff09;数据操作 前言正文一、操作内容处理二、读取数据① 概念② 实操 三、写入数据① 概念② 实操 四、打开通知一、概念二、实操三、收到数据 五、源码 前言 关于低功耗蓝牙的服务、特性、属性、描述符都已经讲清楚了&#xff0c;而下面就是使…...

.netcore grpc双向流方法详解

一、双向流处理概述 简单来讲客户端可以向服务端发送消息流&#xff0c;服务端也可以向客户端传输响应流&#xff0c;即客户端和服务端可以互相通讯客户端无需发送消息即可开始双向流式处理调用 。 客户端可选择使用 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&#xff0c;正确System.out.printl…...

牛客周赛 Round 7

目录 A 游游的you矩阵 题目&#xff1a; 题解&#xff1a; AC 代码&#xff1a; B 游游的01串操作 题目&#xff1a; 题解&#xff1a; AC 代码&#xff1a; C 游游的正整数 题目&#xff1a; 题解&#xff1a; AC 代码&#xff1a; D 游游的选数乘积 题目&#xf…...

R语言生存分析(机器学习)(1)——GBM(梯度提升机)

GBM是一种集成学习算法&#xff0c;它结合了多个弱学习器&#xff08;通常是决策树&#xff09;来构建一个强大的预测模型。GBM使用“Boosting”的技术来训练弱学习器&#xff0c;这种技术是一个迭代的过程&#xff0c;每一轮都会关注之前轮次中预测效果较差的样本&#xff0c;…...

k8s和docker简单介绍

当涉及到容器技术和容器编排时&#xff0c;Docker和Kubernetes是两个重要的概念。我将更详细地介绍它们以及它们之间的关系。 Docker&#xff1a; Docker是一种容器化技术&#xff0c;它允许你将应用程序及其依赖项打包到一个称为"容器"的封闭环境中。每个容器都包…...

Lua学习记录

Lua基础了解 Lua的注释通过 (-- 单行注释&#xff0c;--[[ ]] 多行注释)可以不加&#xff1b; 多个变量赋值&#xff0c;按顺序赋值&#xff0c;没有则为nil&#xff1b; function的简单用法&#xff0c;多个返回值配合多重赋值&#xff0c;以end为结束标志 Lua下标从1开始&…...

三分钟完美解决你的C盘内存过大爆红

一、清理回收站 二、清理桌面 建议一 不要在桌面放太多图标或者文件会占用过多的内存,可以放到其他盘建议二、 将位置移动到别的盘 三、手动删除下载文件与缓存文件 日常使用中会通过Windows下载各种文件资料到电脑中&#xff0c;它默认也是直接下载在C盘中的。如果我们在以…...

C++ - equal(比较两个vector元素)

C标准库的std::equal函数。这个函数用于比较两个范围的元素是否相等。 在使用std::equal函数时&#xff0c;您需要提供两个范围的迭代器&#xff0c;以及一个可选的谓词函数&#xff08;predicate&#xff09;。函数会比较第一个范围内的元素和第二个范围内的元素是否相等。如果…...

多线程:线程池

线程池 提前创建多个线程放入线程池中&#xff0c;使用时直接获取&#xff0c;使用完直接放入池中&#xff1b;可以避免频繁创建销毁&#xff0c;实现重复利用&#xff0c;类似生活中的公共交通工具。好处&#xff1a;提高相应速度&#xff1b;降低资源消耗&#xff1b;便于线…...

9.3.2.2网络原理(传输层TCP)

TCP全部细节参考RFC标准文档 一.TCP特点: 有连接,可靠传输,面向字节流,全双工. 二.TCP数据报: 1.端口号是传输层的重要概念. 2.TCP的报头是变长的(UDP是固定的8字节),大小存在4位首部长度中,用4个bit位(0~15)表示长度单位是4字节.(TCP报头最大长度是60字节,前面20字节是固定…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

基于matlab策略迭代和值迭代法的动态规划

经典的基于策略迭代和值迭代法的动态规划matlab代码&#xff0c;实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...

如何更改默认 Crontab 编辑器 ?

在 Linux 领域中&#xff0c;crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用&#xff0c;用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益&#xff0c;允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...

Git常用命令完全指南:从入门到精通

Git常用命令完全指南&#xff1a;从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能

1. 开发环境准备 ​​安装DevEco Studio 3.1​​&#xff1a; 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK ​​项目配置​​&#xff1a; // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...