剑指 Offer 42. 连续子数组的最大和
剑指 Offer 42. 连续子数组的最大和
难度:easy\color{Green}{easy}easy
题目描述
输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
提示:
- 1<=arr.length<=1051 <= arr.length <= 10^51<=arr.length<=105
- −100<=arr[i]<=100-100 <= arr[i] <= 100−100<=arr[i]<=100
注意:本题与主站 53 题相同:https://leetcode-cn.com/problems/maximum-subarray/
算法
| 常见解法 | 时间复杂度 |
|---|---|
| 暴力搜索 | O(n2)O(n^2)O(n2) |
| 分治思想 | O(nlogn)O(nlogn)O(nlogn) |
| 动态规划 | O(n)O(n)O(n) |
(动态规划)
- 状态定义: 设动态规划列表 dpdpdp ,dp[i]dp[i]dp[i] 代表以元素 nums[i]nums[i]nums[i] 为结尾的连续子数组最大和。
为何定义最大和
dp[i]中必须包含元素nums[i]:保证dp[i]递推到dp[i+1]的正确性;如果不包含nums[i],递推时则不满足题目的 连续子数组 要求。
-
转移方程: 若 dp[i−1]≤0dp[i−1]≤0dp[i−1]≤0 ,说明 dp[i−1]dp[i−1]dp[i−1] 对 dp[i]dp[i]dp[i] 产生负贡献,即 dp[i−1]+nums[i]dp[i−1]+nums[i]dp[i−1]+nums[i] 还不如 nums[i]nums[i]nums[i] 本身大。
- 当 dp[i−1]>0dp[i−1]>0dp[i−1]>0 时:执行 dp[i]=dp[i−1]+nums[i]dp[i]=dp[i−1]+nums[i]dp[i]=dp[i−1]+nums[i] ;
- 当 dp[i−1]≤0dp[i−1]≤0dp[i−1]≤0 时:执行 dp[i]=nums[i]dp[i]=nums[i]dp[i]=nums[i] ;
-
初始状态: dp[0]=nums[0]dp[0]=nums[0]dp[0]=nums[0],即以 nums[0]nums[0]nums[0] 结尾的连续子数组最大和为 nums[0]nums[0]nums[0] 。
-
返回值: 返回 dpdpdp 列表中的最大值,代表全局最大值。

复杂度分析
-
时间复杂度:O(n)O(n)O(n)。
-
空间复杂度 : O(1)O(1)O(1)
C++ 代码
使用 res 代表最终的答案,s 表示前 i - 1 项的值, 如果前 i - 1 项的值小于 0,s 等于当前的数 num,如果大于 0, 说明可以加上当前的数字 num,继续往后运算。
class Solution {
public:int maxSubArray(vector<int>& nums) {int res = INT_MIN, s = 0;for (auto x : nums) {if (s < 0) s = 0;s += x;res = max(res, s);}return res;}
};
参考链接
相关文章:
剑指 Offer 42. 连续子数组的最大和
剑指 Offer 42. 连续子数组的最大和 难度:easy\color{Green}{easy}easy 题目描述 输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。 要求时间复杂度为O(n)。 示例1: 输入: nums [-2,1,-3,4,-1,2,1,-5,4] 输…...
双指针 (C/C++)
1. 双指针 双指针算法的核心思想:将暴力解法的时间复杂度,通常是O(N*N),通过某种特殊的性质优化到O(N)。 做题思路:先想想暴力解法的思路,然后分析这道题的特殊性质,一般是单调性。然后得出双指针算法的思路…...
CVE-2023-23752 Joomla未授权访问漏洞分析
漏洞概要 Joomla 在海外使用较多,是一套使用 PHP 和 MySQL 开发的开源、跨平台的内容管理系统(CMS)。 Joomla 4.0.0 至 4.2.7 版本中的 ApiRouter.php#parseApiRoute 在处理用户的 Get 请求时未对请求参数有效过滤,导致攻击者可向 Joomla 服务端点发送包…...
单通道说话人语音分离——Conv-TasNet(Convolutional Time-domain audio separation Network)
单通道说话人语音分离——Conv-TasNet模型(Convolutional Time-domain audio separation Network) 参考文献:《Conv-TasNet: Surpassing Ideal Time-FrequencyMagnitude Masking for Speech Separation》 1.背景 在真实的声学环境中,鲁棒的语音处理通常…...
华为OD机试真题Python实现【环中最长子串】真题+解题思路+代码(20222023)
环中最长子串 题目 给你一个字符串s,首尾相连成一个环形, 请你在环中找出o字符出现了偶数次最长子字符串的长度. 备注: 1 <= s.lenth <= 5x10^5 s只包含小写英文字母 🔥🔥🔥🔥🔥👉👉👉👉👉👉 华为OD机试(Python)真题目录汇总 ## 输入 输入是…...
Netcat安装与使用(nc)
Netcat安装与使用1.Netcat简介1.1.Netcat安装1.1.1.安装整体流程1.1.1.1.安装依赖1.1.1.2.安装Netcat1.1.1.3.配置环境变量1.1.1.4.测试1.2.Netcat基本功能1.3.Netcat常用参数2.Netcat用法2.1.前期准备2.2.banner相关信息抓取2.3.端口扫描2.3.1.扫描指定端口2.3.2.扫描指定端口…...
蓝桥杯:聪明的猴子
题目链接:聪明的猴子https://www.lanqiao.cn/problems/862/learning/ 目录 题目描述 输入描述 输出描述 输入输出样例 运行限制 解题思路: 最小生成树 AC代码(Java): 课后练习: 题目描述 在一个热带雨林中生存…...
Spring Boot应用如何快速接入Prometheus监控
1. Micrometer简介Micrometer为Java平台上的性能数据收集提供了一个通用的API,它提供了多种度量指标类型(Timers、Guauges、Counters等),同时支持接入不同的监控系统,例如Influxdb、Graphite、Prometheus等。可以通过M…...
vscode远程调试python
目的 注意:这里我们想要实现的是:用vscode 使用remote ssh打开project,然后直接在project里面进行debug,而不需要 在本地vscode目录打开一样的project。 假设大家已经会使用remote ssh打开远程服务器的代码了,那么只…...
Spring Boot 框架 集成 Knife4j(内含源代码)
Spring Boot 框架 集成 Knife4j(内含源代码) 源代码下载链接地址:https://download.csdn.net/download/weixin_46411355/87480176 目录Spring Boot 框架 集成 Knife4j(内含源代码)源代码下载链接地址:[htt…...
什么蓝牙耳机适合打游戏?打游戏不延迟的蓝牙耳机
为了提升游戏体验,除了配置强悍的主机外,与之搭配蓝牙耳机等外设产品也尤为重要,今天就带大家来了解一下以下几款适合玩游戏,低延迟操作的蓝牙耳机。 第一款:南卡小音舱蓝牙耳机 参考价格:239元 推荐理由…...
【项目设计】高并发内存池(一)[项目介绍|内存池介绍|定长内存池的实现]
🎇C学习历程:入门 博客主页:一起去看日落吗持续分享博主的C学习历程博主的能力有限,出现错误希望大家不吝赐教分享给大家一句我很喜欢的话: 也许你现在做的事情,暂时看不到成果,但不要忘记&…...
初识MySQL下载与安装【快速掌握知识点】
目录 前言 MySQL版本 MySQL类型 MySQL官网有.zip和.msi两种安装形式; MySQL 下载 1、MySQL 属于 Oracle 旗下产品,进入Oracle官网下载 2、点击产品,找到MySQL 3、进入MySQL页面 4、点击Download(下载)&#x…...
如何终止一个线程
如何终止一个线程 是使用 thread.stop() 吗? public class ThreadDemo extends Thread{Overridepublic void run() {try {Thread.sleep(10000);} catch (InterruptedException e) {e.printStackTrace();}System.out.println("this is demo thread :"Thre…...
上岸!选择你的隐私计算导师!
开放隐私计算 开放隐私计算开放隐私计算OpenMPC是国内第一个且影响力最大的隐私计算开放社区。社区秉承开放共享的精神,专注于隐私计算行业的研究与布道。社区致力于隐私计算技术的传播,愿成为中国 “隐私计算最后一公里的服务区”。183篇原创内容公众号…...
go gin学习记录5
有了前面几节的学习,如果做个简单的web服务端已经可以完成了。 这节来做一下优化。 我们实验了3种SQL写入的方法,但是发现每一种都需要在方法中去做数据库链接的操作,有些重复了。 所以,我们把这部分提取出来,数据库链…...
PyQt5数据库开发2 5.1 QSqlQueryModel
目录 一、Qt窗体设计 1. 新建Qt项目 2. 拷贝4-3的部分组件过来 3. 添加资源文件 4. 创建Action 5. 添加工具栏 6. 创建菜单项 7. 关闭Action的实现 8. 调整布局 8.1 调整两个groupbox的布局 8.3 为窗体设置全局布局 二、代码拷贝和删除 1. 新建项目目录 2. 编译…...
MySQL-redo log和undo log
什么是事务 事务是由数据库中一系列的访问和更新组成的逻辑执行单元 事务的逻辑单元中可以是一条SQL语句,也可以是一段SQL逻辑,这段逻辑要么全部执行成功,要么全部执行失败 举个最常见的例子,你早上出去买早餐,支付…...
阿里云ECS TOP性能提升超20%!KeenTune助力倚天+Alinux3达成开机即用的全栈性能调优 | 龙蜥技术
文/KeenTune SIG01阿里云 ECS 上售卖页新增“应用加速”功能2023年1月12日 阿里云 ECS 的售卖页有了一些新的变化,在用户选择倚天 Alinux3 新建实例时,多了一个新的选项“应用加速”。这个功能是 阿里云 ECS 基于 KeenTune 提供典型云场景的开机即用的全…...
华为OD机试真题Python实现【快递业务站】真题+解题思路+代码(20222023)
快递业务站 题目 快递业务范围有 N 个站点,A 站点与 B 站点可以中转快递,则认为 A-B 站可达, 如果 A-B 可达,B-C 可达,则 A-C 可达。 现在给 N 个站点编号 0、1、…n-1,用 s[i][j]表示 i-j 是否可达, s[i][j] = 1表示 i-j可达,s[i][j] = 0表示 i-j 不可达。 现用二维…...
大型活动交通拥堵治理的视觉算法应用
大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动(如演唱会、马拉松赛事、高考中考等)期间,城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例,暖城商圈曾因观众集中离场导致周边…...
解锁数据库简洁之道:FastAPI与SQLModel实战指南
在构建现代Web应用程序时,与数据库的交互无疑是核心环节。虽然传统的数据库操作方式(如直接编写SQL语句与psycopg2交互)赋予了我们精细的控制权,但在面对日益复杂的业务逻辑和快速迭代的需求时,这种方式的开发效率和可…...
MMaDA: Multimodal Large Diffusion Language Models
CODE : https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA,它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构…...
【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验
系列回顾: 在上一篇中,我们成功地为应用集成了数据库,并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了!但是,如果你仔细审视那些 API,会发现它们还很“粗糙”:有…...
从零实现STL哈希容器:unordered_map/unordered_set封装详解
本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说,直接开始吧! 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...
JDK 17 新特性
#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持,不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的ÿ…...
C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。
1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj,再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...
学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”
2025年#高考 将在近日拉开帷幕,#AI 监考一度冲上热搜。当AI深度融入高考,#时间同步 不再是辅助功能,而是决定AI监考系统成败的“生命线”。 AI亮相2025高考,40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕,江西、…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...
【 java 虚拟机知识 第一篇 】
目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...
