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

[动规19] 最大子数组和

news 来源：原创 2025/7/2 19:13:10

目录

1. 题意

2. 思路

2.1. 状态表示

2.2. 状态转移方程

2.3. 初始化

2.4. 填表顺序

2.5. 返回值

3. 编码

1. 题意

链接: 53. 最大子数组和 - 力扣（LeetCode）

题目

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

提示：

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

子数组:

2. 思路

2.1. 状态表示

dp[i]: 以 i 位置为结尾, 所有子数组中的最大和.

2.2. 状态转移方程

要分析状态转移方程, 我们先聚焦于一个 dp[i] 位置来进行分析:

整体可以分为两类:

  • 长度 == 1
  • 长度 > 1

所以, 我们的 dp[i] = max(nums[i], nums[i] + dp[i-1]).

2.3. 初始化

因为我们的 dp[i] 依赖 dp[i-1], 因此我们需要初始化 dp[0], 下面提供两种思路:

方式 1: 初始化 dp[0] = nums[0]

方式 2: 添加虚拟节点, dp[0] = 0;// 虚拟节点 -> 不过需要注意下标的映射关系.

2.4. 填表顺序

从左到右(这是状态转移方程所决定的).

2.5. 返回值

返回以 i 位置为结尾的子数组的最大值

for(int i = 0; i < n; i++)
{ret = max(dp[i], ret);
}return ret;

3. 编码

class Solution {
public:int maxSubArray(vector<int>& nums) {// dp[i]表示: 以i位置为结尾, 最大的一个子数组之和// 1. 创建dp表int n = nums.size();vector<int> dp(n+1, 0);// 2. 初始化// 3. 赋值int m = INT_MIN;for(int i = 1; i <= n; i++){dp[i] = max(nums[i-1], dp[i-1] + nums[i-1]);if(dp[i] > m) m = dp[i];}// 4. 返回return m;}
};

注意点:

  1. 略.

相关文章：

[动规19] 最大子数组和

目录 1. 题意 2. 思路 2.1. 状态表示 2.2. 状态转移方程 2.3. 初始化 2.4. 填表顺序 2.5. 返回值 3. 编码 1. 题意 链接: 53. 最大子数组和 - 力扣&#xff08;LeetCode&#xff09; 题目 给你一个整数数组 nums &#xff0c;请你找出一个具有最大和的连续子数组&…...

编程日记 2025/7/2 19:13:10

2024年零知识证明(ZK)研究进展

Sumcheck 整个领域正在转向更多地依赖于 Sumcheck Protocol Sumcheck是用于验证多项式承诺的协议&#xff0c;常用于零知识证明&#xff08;ZKP&#xff09;中&#xff0c;尤其是在可验证计算和扩展性上。它的主要目的是通过对多项式进行分段检查&#xff0c;从而保证某个多项…...

编程日记 2025/7/3 1:21:57

1. 两数之和

leetcode Hot 100系列 文章目录 一、核心操作二、外层配合操作三、核心模式代码总结 一、核心操作 使用map&#xff0c;key作为数值&#xff0c;value作为下标先寻找对应的目标值&#xff0c;如果找到了则直接返回&#xff0c;否则在往map中插入 提示&#xff1a;小白个人理…...

编程日记 2025/7/3 11:17:31

【电动汽车再生制动控制技术（万字长文，图文并茂）】

电动汽车再生制动控制系统概述 电动汽车再生制动的基本原理是:通过具有可逆作用的电动机/发电机来实现电动汽车动能和电能的转化。在汽车减速或制动时，可逆电机以发电机形式工作，汽车行驶的动能带动发电机将汽车动能转化为电能并储存在储能器(蓄电池或超级电容器)中；在汽车…...

编程日记 2025/7/3 13:55:19

python实现股票数据可视化

最近在做一个涉及到股票数据清洗及预测的项目&#xff0c;项目中需要用到可视化股票数据这一功能&#xff0c;这里我与大家分享一下股票数据可视化的一些基本方法。 股票数据获取 目前&#xff0c;我已知的使用python来获取股票数据方式有以下三种: 爬虫获取&#xff0c;实现…...

编程日记 2025/7/3 14:48:33

2025年湖南建筑安全员 C1考证刷题题库

湖南建筑安全员 C1 类的练习题&#xff1a; 1、塔机的拆装作业必须在白天进行&#xff0c;不得在&#xff08; &#xff09;情况下进行。 A. 夜间 B. 大风 C. 浓雾 D. 以上都是 答案&#xff1a;D 2、采用钢筋混凝土灌注桩时&#xff0c;开挖标准是桩身混凝土达到&#…...

编程日记 2025/7/3 14:51:16

【Feign】⭐️使用 openFeign 时传递 MultipartFile 类型的参数参考

&#x1f4a5;&#x1f4a5;✈️✈️欢迎阅读本文章❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;本篇文章阅读大约耗时三分钟。 ⛳️motto&#xff1a;不积跬步、无以千里 &#x1f4cb;&#x1f4cb;&#x1f4cb;本文目录如下&#xff1a;&#x1f381;&#x1f381;&a…...

编程日记 2025/7/3 14:11:36

ToolsSet之：梯度色板

ToolsSet是微软商店中的一款包含数十种实用工具数百种细分功能的工具集合应用&#xff0c;应用基本功能介绍可以查看以下文章&#xff1a; Windows应用ToolsSet介绍https://blog.csdn.net/BinField/article/details/145898264 ToolsSet中Media菜单下的“Gradient Palette”工…...

编程日记 2025/7/3 16:06:53

Apache Hive和Snowflake的`CREATE VIEW`语法和功能特性整理的对比表

写一个Apache Hive中CREATE VIEW语句转换为对应Snowflake中CREATE VIEW语句的程序&#xff0c;现在需要一个根据功能的相似性对应的Apache HiveQL和Snowflake SQL的CREATE VIEW语句的表。 以下是基于Apache Hive的CREATE VIEW语法规则构造的所有可能合法语句实例及其功能说明&…...

编程日记 2025/7/3 15:15:45

【测试】每日3道面试题 3/31

长期更新&#xff0c;建议关注收藏点赞。 单元测试策略有哪些&#xff0c;主要内容。 白盒测试黑盒测试基于异常和边界的测试 主要内容&#xff1a;测试用例设计、执行、结果分析、自动化beta测试和alpha测试主要区别 主要区别&#xff1a;测试环境测试者 alphabeta时间先后测…...

编程日记 2025/6/28 5:13:26

用 Hugging Face Spaces 打造哪吒的 3D 模型：完整指南

引言&#xff1a; 哪吒&#xff0c;这位中国神话中的传奇人物&#xff0c;以其独特的形象和故事深受人们喜爱。如今&#xff0c;通过 Hugging Face Spaces 提供的 TripoSG 工具&#xff0c;我们可以轻松创建哪吒的 3D 模型。以下是详细步骤&#xff0c;帮助你将这个神话角色带入…...

编程日记 2025/7/2 3:59:54

鸿蒙应用元服务开发-Account Kit概述

Account Kit&#xff08;华为账号服务&#xff09;提供简单、快速、安全的登录功能&#xff0c;让用户快捷地使用华为账号登录元服务。用户授权后&#xff0c;Account Kit可提供头像、手机号码等信息&#xff0c;帮助元服务更了解用户。Account Kit提供的SampleCode示例工程体现…...

编程日记 2025/7/2 4:24:10

美团小程序 mtgsig1.2 拼好饭案例 分析 mtgsig

声明 本文章中所有内容仅供学习交流使用&#xff0c;不用于其他任何目的&#xff0c;抓包内容、敏感网址、数据接口等均已做脱敏处理&#xff0c;严禁用于商业用途和非法用途&#xff0c;否则由此产生的一切后果均与作者无关&#xff01; 逆向分析 美团网页、小程序、app全是指…...

编程日记 2025/6/28 5:10:18

hadoop集群和常用命令

Hadoop集群的搭建与管理 1. HADOOP简介 Hadoop 是一种用于大规模数据处理的大数据框架&#xff0c;支持通过简单编程模型实现跨计算机集群的数据分布存储和计算3。 2. HADOOP集群部署过程 (1) 解压并安装HADOOP 在虚拟机环境中&#xff0c;可以通过解压缩方式完成Hadoop的安…...

编程日记 2025/7/2 19:12:07

爬虫：基本流程和robots协议

基本流程&#xff1a; 1.确认目标&#xff1a;url:www.baidu.com 2.发送请求&#xff1a;发送网络请求&#xff0c;获取到特定的服务端给你的响应 3.提取数据&#xff1a;从响应中提取特定的数据 4.保存数据&#xff1a;本地(html,json,txt)&#xff0c;数据库 获取到的响应…...

编程日记 2025/6/28 5:19:01

python之三种去重方法

1. 数据读取与参数解析 代码片段 detail pd.read_csv(detail.csv, index_col0, encodinggbk)数据实例 参数详解 index_col0&#xff1a; 作用&#xff1a;将第1列设置为索引其他选项&#xff1a; None&#xff1a;不指定索引列&#xff08;默认&#xff09;列序号/列名&…...

编程日记 2025/6/28 5:25:43

QML输入控件: TextField（文本框）的样式定制

目录 引言示例简介示例代码与关键点示例1&#xff1a;基础样式定制示例2&#xff1a;添加图标示例3&#xff1a;交互式元素&#xff08;清除按钮&#xff09; 实现要点总结完整工程下载 引言 在Qt Quick应用程序开发中&#xff0c;文本输入是最常见的用户交互方式之一。TextFi…...

编程日记 2025/6/28 2:24:29

Visual Studio | 性能探测器

文章目录 一、性能探测器1、核心功能2、数据采集3、数据分析3.1、CPU分析 前言&#xff1a; Visual Studio&#xff08;VS&#xff09;提供的性能探测器&#xff08;Performance Profiler&#xff09;是一款强大的工具&#xff0c;它能够帮助开发者分析应用程序的性能&#xff…...

编程日记 2025/7/3 4:13:02

数据库中的函数：高效操作与灵活运用

数据库中的函数&#xff1a;高效操作与灵活运用 在数据库开发过程中&#xff0c;函数是常用的工具&#xff0c;可以帮助我们更高效地处理和操作数据。无论是对字符串、数值、日期还是流程控制&#xff0c;数据库函数都能够提供强大的支持。本文将深入探讨常见的数据库函数&…...

编程日记 2025/6/28 1:30:04

《非暴力沟通》第十二章 “重获生活的热情” 总结

《非暴力沟通》第十二章 “重获生活的热情” 的核心总结&#xff1a; 本章将非暴力沟通的核心理念延伸至生命意义的探索&#xff0c;提出通过觉察与满足内心深处的需要&#xff0c;打破“义务性生存”的桎梏&#xff0c;让生活回归由衷的喜悦与创造。作者强调&#xff0c;当行动…...

编程日记 2025/7/2 1:36:13

C++位运算精要：高效解题的利器

引言 在算法竞赛和底层开发中&#xff0c;位运算&#xff08;Bit Manipulation&#xff09;因其极高的执行效率而广受青睐。它能在O(1)时间复杂度内完成某些复杂操作&#xff0c;大幅优化程序性能。本文系统梳理C位运算的核心技巧&#xff0c;涵盖基础操作、经典应用、优化策略…...

编程日记 2025/7/3 1:11:53

从两种遍历方法中构造二叉树

从前序与中序遍历序列构造二叉树 题目描述 代码实现 class Solution { private:unordered_map<int, int> mapIn;TreeNode* dfs(vector<int>& preorder, vector<int>& inorder, int pre_left, int pre_right, int in_left, int in_right){//出口if(…...

编程日记 2025/7/2 23:24:29

【C语言】字符函数的易错点及其模拟实现

在上一章为大家简单介绍了字符函数的种类和基础运用&#xff0c;语法。那么在本章为大家分享一些易错点和自己如何编写一个自定义函数来实现相同的作用。&#xff08;点个关注呗&#xff09; 一strlen&#xff1a;计算字符串长度 1. 函数原型 size_t strlen(const char *str…...

编程日记 2025/7/3 16:58:23

【前端】创建一个vue3+JavaScript项目流程

1、检查node和npm是否安装&#xff0c;查看版本&#xff1a; node -v npm -v 2、安装脚手架cli或vite &#xff08;1&#xff09;cli 安装&#xff1a;npm install -g vue/cli 检查是否安装成功&#xff1a;vue -v 使用cli创建项目&#xff1a;vue create my-project(项目名)--…...

编程日记 2025/6/29 13:50:17

JVM面试专题

目录 1 JVM组成 1.1 JVM由那些部分组成&#xff0c;运行流程是什么&#xff1f; 1.2 什么是程序计数器&#xff1f; 1.3 你能给我详细的介绍Java堆吗? 元空间(MetaSpace)介绍 1.4 什么是虚拟机栈 1.5 方法区 1.5.1 概述 1.5.2 常量池 1.5.3 运行时常量池 1.6 你听过…...

编程日记 2025/7/3 16:44:06

齐次线性方程组及python求解

齐次线性方程组的概念 齐次线性方程组是指所有常数项都为零的线性方程组&#xff0c;其一般形式为&#xff1a; a 11 x 1 a 12 x 2 ⋯ a 1 n x n 0 a_{11}x_1 a_{12}x_2 \cdots a_{1n}x_n 0 a11​x1​a12​x2​⋯a1n​xn​0 a 21 x 1 a 22 x 2 ⋯ a 2 n x n 0 a_…...

编程日记 2025/7/3 15:25:14

鸿蒙前后端项目源码-点餐v3.0-原创!原创!原创!

鸿蒙前后端点餐项目源码含文档ArkTS语言. 原创作品.我半个月写的原创作品&#xff0c;请尊重原创。 原创作品&#xff0c;盗版必究&#xff01;&#xff01;&#xff01;&#xff01; 原创作品&#xff0c;盗版必究&#xff01;&#xff01;&#xff01;&#xff01; 原创作…...

编程日记 2025/7/3 1:09:17

【数据结构】算法效率的双刃剑：时间复杂度与空间复杂度

前言 在算法的世界里&#xff0c;效率是衡量算法优劣的关键标准。今天&#xff0c;就让我们深入探讨算法效率的两个核心维度&#xff1a;时间复杂度和空间复杂度&#xff0c;帮助你在算法设计的道路上更进一步。 一、算法效率&#xff1a;衡量算法好坏的关键 算法的效率主要…...

编程日记 2025/7/3 1:16:42

Linux | I.MX6ULL 终结者底板原理图讲解(5)

01 USB 转串口电路 I.MX6ULL 终结者开发板板载了一个 USB 串口，原理图如图 1 和图 2 所示： USB 转串口我们使用的是 CH340G 芯片，该芯片是由南京沁恒微电子研发生产的一款国产芯片。CH340G的工作电压支持 3.3V、5V，甚至是 3V，从上图可以看到我们给 CH340G 的电压是 5V…...

编程日记 2025/7/3 4:22:08

java拆分字符串、去重并统计相关长度

java拆分字符串、去重并统计相关长度 20250331 19:52 求取逗号隔开的字符串的 的长度&#xff0c;要求去重。拆分字符串应该是指按照某种分隔符将字符串分割成多个部分&#xff0c;然后去除重复的部分&#xff0c;最后统计处理后各个部分的长度或者总长度。 这时候可能需要明确…...

编程日记 2025/7/3 15:13:57

Vue 2 和 Vue 3 有什么区别

Vue 2 和 Vue 3 是 Vue.js 框架的两个主要版本&#xff0c;它们在核心特性、性能、API 设计等方面有一些显著的区别。以下是它们的主要区别&#xff1a; 1. 核心特性 • Composition API&#xff1a; • Vue 3 引入了 Composition API&#xff0c;这是一种新的 API&#xff0…...

编程日记 2025/7/3 16:03:20

RabbitMQ、RocketMQ 和 Kafka 的消息特性对比

以下是 RabbitMQ、RocketMQ 和 Kafka 在保证消息不丢失、消息顺序、消息幂等性以及快速处理积压方面的详细对比&#xff1a; 1. 消息不丢失 特性RabbitMQRocketMQKafka生产者端开启事务或 Confirm 模式使用事务消息机制设置 acksall 确保消息被所有副本确认服务端消息持久化&…...

编程日记 2025/6/29 10:55:37

Logback 实现不同包的日志记录到不同文件

核心 通过合理配置多个 appender 来定义不同的日志输出目的地通过 logger 元素将不同的包与对应的 appender 关联起来同时利用 additivity 属性控制日志的传递&#xff0c;从而实现精准的日志输出管理。 additivity 属性控制日志传递&#xff1a; additivity 属性决定了该 l…...

编程日记 2025/7/2 19:13:01

【附JS、Python、C++题解】Leetcode面试150题（11）H指数

一、题目 274. H 指数 给你一个整数数组 citations &#xff0c;其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。 根据维基百科上 h 指数的定义&#xff1a;h 代表“高引用次数” &#xff0c;一名科研人员的 h 指数 是指他&#xf…...

编程日记 2025/7/2 4:20:28

C++第13届蓝桥杯省b组习题笔记

1.九进制转十进制 九进制正整数 (2022)9转换成十进制等于多少&#xff1f; 第一位乘9的0次方&#xff0c;第二位乘9的1次方&#xff0c;第三位乘9的二次方以此类推 #include <iostream> using namespace std;int main() {// 请在此输入您的代码int t2022;int res0;int c…...

编程日记 2025/6/30 10:26:42

【学Rust写CAD】19 颜色渐变定义（gradient_stop.rs）

源码 //color/gradient_stop.rs use super::argb::Color; #[derive(Clone, Copy, Debug)] pub struct GradientStop {pub position: f32,pub color: Color, }代码分析 这段代码是一个结构体&#xff08;struct&#xff09;&#xff0c;并为其派生&#xff08;derive&#xff…...

编程日记 2025/7/3 8:57:57

从零开始跑通3DGS教程：介绍

写在前面 本文内容 本文所属《从零开始跑通3DGS教程》系列文章&#xff0c;将实现从原始图像(有序、无序)数据开始&#xff0c;经过处理(视频抽帧成有序)&#xff0c;SFM&#xff0c;3DGS训练、编辑、渲染等步骤&#xff0c;完整地呈现从原始图像到新视角合成的全部流程&#x…...

编程日记 2025/7/1 18:17:18

探索 Python 编程的宇宙：从基础到进阶的奇妙之旅

在当今的编程世界里&#xff0c;Python 以其简洁、易读和强大的功能&#xff0c;成为了众多开发者的心头好。它就像一个充满无限可能的宇宙&#xff0c;吸引着人们不断去探索其中的奥秘。今天&#xff0c;让我们一起踏上这场 Python 编程的奇妙之旅&#xff0c;从基础到进阶&am…...

编程日记 2025/6/30 7:08:41

使用 Spring AI 和 LangChain4j 实现聊天机器人对比分析

人工智能领域正在彻底改变公司管理客户服务的方式。随着 Spring AI 和 LangChain4j 等专用框架的出现&#xff0c;Java 开发人员现在拥有强大的工具来实现能够从公司数据中学习的智能聊天机器人。在本文中&#xff0c;我们将探讨这两个框架的主要功能&#xff0c;并了解如何使用…...

编程日记 2025/7/3 4:13:02

3月31（信息差）

1.全国首个！湖北为脑机接口医疗服务定价 据湖北省医疗保障局消息，今日，湖北省医保局发布全国首个脑机接口医疗服务价格，其中，侵入式脑机接口植入费6552 元/次，侵入式脑机接口取出费3139元/次，非侵入式脑机接口适配费966元/次，标志着这一前沿科技正式步入民生领域，为无…...

编程日记 2025/6/28 4:28:52

苍穹外卖项目结构

苍穹外卖项目总结-CSDN博客 【苍穹外卖|项目】万字总结-CSDN博客 苍穹外卖项目总结_苍芎外卖如何实现的跨域-CSDN博客 【苍穹外卖 | 项目日记】第九天 万字总结-CSDN博客 【苍穹外卖|项目】万字总结-CSDN博客 一、技术点&#xff1a; Nginx代理 负载均衡&#xff1a;通过…...

编程日记 2025/7/2 7:53:03

3. 无重复字符的最长子串

leetcode Hot 100系列 文章目录 一、核心操作二、外层配合操作三、核心模式代码总结 一、核心操作 用map&#xff0c;key为char&#xff0c;value为出现次数&#xff0c;将字符串中的值依次入栈&#xff0c;再判断次数是否大于1&#xff0c;如果大于1&#xff0c;则循环删除掉…...

编程日记 2025/7/1 18:30:45

python力扣48.旋转图像

给定一个 n n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。 你必须在 原地 旋转图像&#xff0c;这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。 示例 1&#xff1a; 输入&#xff1a;matrix [[1,2,3],[4,5,6],[7,8,9]] 输出&…...

编程日记 2025/7/3 6:55:55

文章配图新纪元：OpenAI新推出的GPT-4o原生图像生成功能启示

当OpenAI推出GPT-4o原生图像生成功能时&#xff0c;许多人惊呼&#xff1a;“AI生成的图像已经发展到这样了吗&#xff01;”这一激动人心的时刻&#xff0c;标志着人工智能在图像创作领域迈出了历史性的一步。无论是细腻的人物肖像&#xff0c;栩栩如生的面部表情&#xff0c;…...

编程日记 2025/6/30 8:06:35

使用Google Gemini API密钥创建AI驱动的Chrome扩展程序

在这个快节奏的数字时代，我们高度依赖Chrome扩展程序来提升浏览效率。 但你是否想过用人工智能为你的扩展注入超能力？听起来很酷对吧？😎 随着谷歌Gemini API的发布，AI技术变得触手可及。 该API能让你在项目中直接调用先进的自然语言处理、图像识别等炫酷的AI功能。 更…...

编程日记 2025/6/29 7:49:21

MapReduce的工作原理

MapReduce 是 Hadoop 的核心计算框架&#xff0c;用于分布式处理大规模数据集。它的核心思想是 **"分而治之"**&#xff0c;将任务拆分为多个子任务并行处理&#xff0c;最终汇总结果。以下是其工作原理的详细解析 1. 核心阶段 MapReduce 的执行过程分为三个阶段&a…...

编程日记 2025/6/28 1:25:02

k8s网络策略

k8s网络策略 k8s网络测试概述查看防火墙策略 k8s网络策略网络访问控制案例&#xff1a;配置k8s网络策略结果验证 k8s网络策略配置示例 k8s网络测试概述 网络策略就是设置防火墙 查看防火墙策略 # 获取当前命名空间下的所有 NetworkPolicy 资源&#xff08;网络策略&#xff0…...

编程日记 2025/7/2 13:16:47

Linux文件描述符的分配机制与重定向实现：揭开“一切皆文件”的面纱

Linux系列 文章目录 Linux系列前言一、Linux的标准流二、文件描述符分配规则三、文件重定向四、Linux下一切皆文件 前言 上篇我们介绍了语言和系统层次的基础I/O文件操作&#xff0c;其涉及的知识有&#xff1a;C语言文件操作和系统调用接口两者的关系、文件描述符的概念、操作…...

编程日记 2025/6/29 5:50:34

SpringBoot事务管理（四）

记录几条SpringBoot事务管理中踩过的坑及解决办法&#xff1a; 1. 自调用问题 问题描述 在同一个类中&#xff0c;一个非事务方法调用另一个有 Transactional 注解的事务方法&#xff0c;事务不会生效。因为 Spring 的事务管理是基于 AOP 代理实现的&#xff0c;自调用时不会…...

编程日记 2025/7/3 7:02:13

iOS GCD

GCD 任务队列 主队列&#xff1a; 任务在主线程执行&#xff0c;主队列是一个串行队列&#xff0c;它主要处理 UI 相关任务&#xff0c;也可以处理其他类型任务&#xff0c;但为了性能考虑&#xff0c;尽量让主队列执行 UI 相关或少量不耗时间和资源的操作。 系统全局并发队…...

编程日记 2025/6/27 18:05:37