剑指 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 不可达。 现用二维…...
在软件开发中正确使用MySQL日期时间类型的深度解析
在日常软件开发场景中,时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志,到供应链系统的物流节点时间戳,时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库,其日期时间类型的…...
Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件
今天呢,博主的学习进度也是步入了Java Mybatis 框架,目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学,希望能对大家有所帮助,也特别欢迎大家指点不足之处,小生很乐意接受正确的建议&…...
STM32+rt-thread判断是否联网
一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...
电脑插入多块移动硬盘后经常出现卡顿和蓝屏
当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时,可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案: 1. 检查电源供电问题 问题原因:多块移动硬盘同时运行可能导致USB接口供电不足&#x…...
06 Deep learning神经网络编程基础 激活函数 --吴恩达
深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...
爬虫基础学习day2
# 爬虫设计领域 工商:企查查、天眼查短视频:抖音、快手、西瓜 ---> 飞瓜电商:京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空:抓取所有航空公司价格 ---> 去哪儿自媒体:采集自媒体数据进…...
【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分
一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计,提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合:各模块职责清晰,便于独立开发…...
全面解析各类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…...
是否存在路径(FIFOBB算法)
题目描述 一个具有 n 个顶点e条边的无向图,该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序,确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数,分别表示n 和 e 的值(1…...
项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)
Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败,具体原因是客户端发送了密码认证请求,但Redis服务器未设置密码 1.为Redis设置密码(匹配客户端配置) 步骤: 1).修…...
