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

剑指 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] <= 100100<=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)

(动态规划)

  • 状态定义: 设动态规划列表 dpdpdpdp[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[i1]0 ,说明 dp[i−1]dp[i−1]dp[i1]dp[i]dp[i]dp[i] 产生负贡献,即 dp[i−1]+nums[i]dp[i−1]+nums[i]dp[i1]+nums[i] 还不如 nums[i]nums[i]nums[i] 本身大。

    • dp[i−1]>0dp[i−1]>0dp[i1]>0 时:执行 dp[i]=dp[i−1]+nums[i]dp[i]=dp[i−1]+nums[i]dp[i]=dp[i1]+nums[i]
    • dp[i−1]≤0dp[i−1]≤0dp[i1]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 项的值小于 0s 等于当前的数 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. 连续子数组的最大和 难度&#xff1a;easy\color{Green}{easy}easy 题目描述 输入一个整型数组&#xff0c;数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。 要求时间复杂度为O(n)。 示例1: 输入: nums [-2,1,-3,4,-1,2,1,-5,4] 输…...

双指针 (C/C++)

1. 双指针 双指针算法的核心思想&#xff1a;将暴力解法的时间复杂度&#xff0c;通常是O(N*N)&#xff0c;通过某种特殊的性质优化到O(N)。 做题思路&#xff1a;先想想暴力解法的思路&#xff0c;然后分析这道题的特殊性质&#xff0c;一般是单调性。然后得出双指针算法的思路…...

CVE-2023-23752 Joomla未授权访问漏洞分析

漏洞概要 Joomla 在海外使用较多&#xff0c;是一套使用 PHP 和 MySQL 开发的开源、跨平台的内容管理系统(CMS)。 Joomla 4.0.0 至 4.2.7 版本中的 ApiRouter.php#parseApiRoute 在处理用户的 Get 请求时未对请求参数有效过滤&#xff0c;导致攻击者可向 Joomla 服务端点发送包…...

单通道说话人语音分离——Conv-TasNet(Convolutional Time-domain audio separation Network)

单通道说话人语音分离——Conv-TasNet模型(Convolutional Time-domain audio separation Network) 参考文献&#xff1a;《Conv-TasNet: Surpassing Ideal Time-FrequencyMagnitude Masking for Speech Separation》 1.背景 在真实的声学环境中&#xff0c;鲁棒的语音处理通常…...

华为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.扫描指定端口…...

蓝桥杯:聪明的猴子

题目链接&#xff1a;聪明的猴子https://www.lanqiao.cn/problems/862/learning/ 目录 题目描述 输入描述 输出描述 输入输出样例 运行限制 解题思路&#xff1a; 最小生成树 AC代码&#xff08;Java&#xff09;: 课后练习&#xff1a; 题目描述 在一个热带雨林中生存…...

Spring Boot应用如何快速接入Prometheus监控

1. Micrometer简介Micrometer为Java平台上的性能数据收集提供了一个通用的API&#xff0c;它提供了多种度量指标类型&#xff08;Timers、Guauges、Counters等&#xff09;&#xff0c;同时支持接入不同的监控系统&#xff0c;例如Influxdb、Graphite、Prometheus等。可以通过M…...

vscode远程调试python

目的 注意&#xff1a;这里我们想要实现的是&#xff1a;用vscode 使用remote ssh打开project&#xff0c;然后直接在project里面进行debug&#xff0c;而不需要 在本地vscode目录打开一样的project。 假设大家已经会使用remote ssh打开远程服务器的代码了&#xff0c;那么只…...

Spring Boot 框架 集成 Knife4j(内含源代码)

Spring Boot 框架 集成 Knife4j&#xff08;内含源代码&#xff09; 源代码下载链接地址&#xff1a;https://download.csdn.net/download/weixin_46411355/87480176 目录Spring Boot 框架 集成 Knife4j&#xff08;内含源代码&#xff09;源代码下载链接地址&#xff1a;[htt…...

什么蓝牙耳机适合打游戏?打游戏不延迟的蓝牙耳机

为了提升游戏体验&#xff0c;除了配置强悍的主机外&#xff0c;与之搭配蓝牙耳机等外设产品也尤为重要&#xff0c;今天就带大家来了解一下以下几款适合玩游戏&#xff0c;低延迟操作的蓝牙耳机。 第一款&#xff1a;南卡小音舱蓝牙耳机 参考价格&#xff1a;239元 推荐理由…...

【项目设计】高并发内存池(一)[项目介绍|内存池介绍|定长内存池的实现]

&#x1f387;C学习历程&#xff1a;入门 博客主页&#xff1a;一起去看日落吗持续分享博主的C学习历程博主的能力有限&#xff0c;出现错误希望大家不吝赐教分享给大家一句我很喜欢的话&#xff1a; 也许你现在做的事情&#xff0c;暂时看不到成果&#xff0c;但不要忘记&…...

初识MySQL下载与安装【快速掌握知识点】

目录 前言 MySQL版本 MySQL类型 MySQL官网有.zip和.msi两种安装形式&#xff1b; MySQL 下载 1、MySQL 属于 Oracle 旗下产品&#xff0c;进入Oracle官网下载 2、点击产品&#xff0c;找到MySQL 3、进入MySQL页面 4、点击Download&#xff08;下载&#xff09;&#x…...

如何终止一个线程

如何终止一个线程 是使用 thread.stop() 吗&#xff1f; 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是国内第一个且影响力最大的隐私计算开放社区。社区秉承开放共享的精神&#xff0c;专注于隐私计算行业的研究与布道。社区致力于隐私计算技术的传播&#xff0c;愿成为中国 “隐私计算最后一公里的服务区”。183篇原创内容公众号…...

go gin学习记录5

有了前面几节的学习&#xff0c;如果做个简单的web服务端已经可以完成了。 这节来做一下优化。 我们实验了3种SQL写入的方法&#xff0c;但是发现每一种都需要在方法中去做数据库链接的操作&#xff0c;有些重复了。 所以&#xff0c;我们把这部分提取出来&#xff0c;数据库链…...

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语句&#xff0c;也可以是一段SQL逻辑&#xff0c;这段逻辑要么全部执行成功&#xff0c;要么全部执行失败 举个最常见的例子&#xff0c;你早上出去买早餐&#xff0c;支付…...

阿里云ECS TOP性能提升超20%!KeenTune助力倚天+Alinux3达成开机即用的全栈性能调优 | 龙蜥技术

文/KeenTune SIG01阿里云 ECS 上售卖页新增“应用加速”功能2023年1月12日 阿里云 ECS 的售卖页有了一些新的变化&#xff0c;在用户选择倚天 Alinux3 新建实例时&#xff0c;多了一个新的选项“应用加速”。这个功能是 阿里云 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 不可达。 现用二维…...

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

selenium学习实战【Python爬虫】

selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...

【Linux】Linux 系统默认的目录及作用说明

博主介绍&#xff1a;✌全网粉丝23W&#xff0c;CSDN博客专家、Java领域优质创作者&#xff0c;掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围&#xff1a;SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...

iview框架主题色的应用

1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题&#xff0c;无需引入&#xff0c;直接可…...

Spring Security 认证流程——补充

一、认证流程概述 Spring Security 的认证流程基于 过滤器链&#xff08;Filter Chain&#xff09;&#xff0c;核心组件包括 UsernamePasswordAuthenticationFilter、AuthenticationManager、UserDetailsService 等。整个流程可分为以下步骤&#xff1a; 用户提交登录请求拦…...

JDK 17 序列化是怎么回事

如何序列化&#xff1f;其实很简单&#xff0c;就是根据每个类型&#xff0c;用工厂类调用。逐个完成。 没什么漂亮的代码&#xff0c;只有有效、稳定的代码。 代码中调用toJson toJson 代码 mapper.writeValueAsString ObjectMapper DefaultSerializerProvider 一堆实…...

【51单片机】4. 模块化编程与LCD1602Debug

1. 什么是模块化编程 传统编程会将所有函数放在main.c中&#xff0c;如果使用的模块多&#xff0c;一个文件内会有很多代码&#xff0c;不利于组织和管理 模块化编程则是将各个模块的代码放在不同的.c文件里&#xff0c;在.h文件里提供外部可调用函数声明&#xff0c;其他.c文…...

【java面试】微服务篇

【java面试】微服务篇 一、总体框架二、Springcloud&#xff08;一&#xff09;Springcloud五大组件&#xff08;二&#xff09;服务注册和发现1、Eureka2、Nacos &#xff08;三&#xff09;负载均衡1、Ribbon负载均衡流程2、Ribbon负载均衡策略3、自定义负载均衡策略4、总结 …...