(动态规划) 剑指 Offer 42. 连续子数组的最大和 ——【Leetcode每日一题】
❓ 剑指 Offer 42. 连续子数组的最大和
难度:简单
输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为 O(n)。
示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
提示:
- 1 < = a r r . l e n g t h < = 1 0 5 1 <= arr.length <= 10^5 1<=arr.length<=105
- $-100 <= arr[i] <= 100
注意:本题与 53. 最大子数组和 相同。
💡思路:动态规划
定义 dp 数组, dp[i]代表以元素 nums[i] 为结尾的连续子数组最大和。
- 若
dp[i−1] < 0,说明dp[i−1]对dp[i]产生负贡献,即dp[i−1]+nums[i]还不如nums[i]本身大。- 当
dp[i−1]>=0时,执行:
d p [ i ] = d p [ i − 1 ] + n u m s [ i ] dp[i]=dp[i−1]+nums[i] dp[i]=dp[i−1]+nums[i] - 当
dp[i−1]<0时,执行 :
d p [ i ] = n u m s [ i ] dp[i]=nums[i] dp[i]=nums[i]
- 当
- 初始状态:
dp[0]=nums[0],即以nums[0]结尾的连续子数组最大和为nums[0]。
优化:
- 观察发现
dp[i]只与dp[i−1]和nums[i]有关系,因此可以第一个变量sum存储dp[i]的值,即存储以元素nums[i]为结尾的连续子数组最大和。 - 由于省去
dp列表使用的额外空间,因此空间复杂度从 O ( n ) O(n) O(n) 降至 O ( 1 ) O(1) O(1)。
🍁代码:(C++、Java)
C++
class Solution {
public:int maxSubArray(vector<int>& nums) {int ans = nums[0];int sum = 0;for(int num : nums){sum = sum < 0 ? num : sum + num;ans = max(ans, sum);}return ans;}
};
Java
class Solution {public int maxSubArray(int[] nums) {int ans = nums[0];int sum = 0;for(int num : nums){sum = sum < 0 ? num : sum + num;ans = Math.max(ans, sum);}return ans;}
}
🚀 运行结果:

🕔 复杂度分析:
- 时间复杂度: O ( n ) O(n) O(n),其中
n为数组nums的长度,我们只需要遍历一遍数组即可求得答案。 - 空间复杂度: O ( 1 ) O(1) O(1),我们只需要常数空间存放若干变量。
题目来源:力扣。
放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!
注: 如有不足,欢迎指正!
相关文章:
(动态规划) 剑指 Offer 42. 连续子数组的最大和 ——【Leetcode每日一题】
❓ 剑指 Offer 42. 连续子数组的最大和 难度:简单 输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。 要求时间复杂度为 O(n)。 示例1: 输入: nums [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1…...
OLED透明屏曲面技术:创新突破引领显示行业未来
OLED透明屏曲面技术作为一项重要的显示技术创新,正在成为显示行业的焦点,其引人注目的优势和广泛应用领域使其备受关注。 本文将详细介绍OLED透明屏曲面技术的优势、应用领域以及市场前景,同时展望其未来的发展趋势,以期带给读者…...
视频云存储/安防监控EasyCVR视频汇聚平台分发rtsp流时,出现“用户已过期”提示该如何解决?
视频云存储/安防监控EasyCVR视频汇聚平台基于云边端智能协同,支持海量视频的轻量化接入与汇聚、转码与处理、全网智能分发、视频集中存储等。音视频流媒体视频平台EasyCVR拓展性强,视频能力丰富,具体可实现视频监控直播、视频轮播、视频录像、…...
调用paddleocr接口实现文本检测与识别,并在图像中显示识别结果
目录 一、按照官网步骤安装paddlepaddle和paddleocr(paddlepaddle我安装的是cpu版本) 二、运行下面的脚本 三、图像结果 一、按照官网步骤安装paddlepaddle和paddleocr(paddlepaddle我安装的是cpu版本) doc/doc_ch/quickstart.md PaddlePaddle/PaddleOCR - Gitee.com 二、…...
如何提升winform程序性能
提升WinForms程序性能是一个关键的优化任务,以下是一些可以帮助你提升性能的方法: 1. **UI延迟加载:** 如果你的WinForms界面很复杂,可以考虑将不必要的UI元素延迟加载,只在需要时加载,以减少启动时间和内…...
按钮权限控制
搜索关键字: 自定义指令传参| "自定义指令""dataset"|自定义指令dataset| "Vue""directives"|vue按钮权限实现 1、完整代码: <template> <div> <el-breadcrumb separator-class"el-icon…...
【脚本式设置环境变量】
在linux系统中,如果我打开一个软件需要如下操作,那将会是一件很麻烦的事情 cd dir #软件的文件路径 conda deactivate conda activate chatgpt python main.py【首先写一个chatgpt.sh脚本内容如下】 #!/bin/bash cd dir conda run -n chatgpt python m…...
软件开发bug问题跟踪与管理
一、Redmine 项目管理和缺陷跟踪工具 官网:https://www.redmine.org/ Redmine 是一个开源的、基于 Web 的项目管理和缺陷跟踪工具。它用日历和甘特图辅助项目及进度可视化显示,同时它又支持多项目管理。Redmine 是一个自由开源软件解决方案,…...
springboot+mp完成简单案例
目录 1.框架搭建 2.前端搭建 3.后端编写 需求:完成简单的连表条件查询以及添加即可 1.框架搭建 1.创建springboot项目 2.相关依赖 <!--web依赖--><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boo…...
cuml机器学习GPU库 sklearn升级版AutoDL使用
CUML库 最近在做机器学习任务的时候发现我自己的数据集太大,直接用sklearn 跑起来时间很长,然后问GPT得知了有CUML库,后来去研究了一下,发现这个库只支持linux系统,从官网直接获取下载命令基本上也实现不了最后&#…...
C语言练习题Day1
从今天开始分享C语言的练习题,每天都分享,差不多持续16天,看完对C语言的理解可能更进一步,让我们开始今天的分享吧! 题目一 执行下面的代码,输出结果是() int x5,y7; void swap()…...
使用kubeadm安装和设置Kubernetes(k8s)
用kubeadm方式搭建K8S集群 kubeadm是官方社区推出的一个用于快速部署kubernetes集群的工具。 这个工具能通过两条指令完成一个kubernetes集群的部署: # 创建一个 Master 节点 kubeadm init# 将一个 Node 节点加入到当前集群中 kubeadm join <Master节点的IP和端口…...
Docker安装延迟队列插件
下载插件地址:https://www.rabbitmq.com/community-plugins.html 插件上传服务器 选择跟我们rabbitmq版本一致或者小于的插件即可。版本可在web管理首页查看。 将下载的插件上传到Linux系统上,使用 docker 命令将插件复制到容器内部 plugins目录下 do…...
推荐前 6 名 JavaScript 和 HTML5 游戏引擎
推荐:使用 NSDT场景编辑器 助你快速搭建3D应用场景 事实是,自从引入JavaScript WebGL API以来,现代浏览器具有直观的功能,使它们能够渲染更复杂和复杂的2D和3D图形,而无需依赖第三方插件。 你可以用纯粹的JavaScript开…...
【Django】 Task5 DefaultRouter路由组件和自定义函数
文章目录 【Django】 Task5 DefaultRouter路由组件和自定义函数1.路由组件1.1路由组件介绍1.2SimpleRouter1.3DefaultRouter1.4DefaultRouter示例1.5查看访问服务接口url 2.自定义函数 【Django】 Task5 DefaultRouter路由组件和自定义函数 Task5 主要了解了DefaultRouter路由…...
Git拉取分支、基于主分支创建新的开发分支、合并开发分支到主分支、回退上一次的merge操作
系列文章目录 第1章 Git拉取分支、基于主分支创建新的开发分支、合并开发分支到主分支、回退上一次的merge操作 文章目录 系列文章目录一、拉取分支二、如何从master分支创建一个dev分支三、如何将dev分支合并到master分支四、如何回退上一次的merge 一、拉取分支 项目文件夹…...
SpringBoot实现定时任务操作及cron在线生成器
spring根据定时任务的特征,将定时任务的开发简化到了极致。怎么说呢?要做定时任务总要告诉容器有这功能吧,然后定时执行什么任务直接告诉对应的bean什么时间执行就行了,就这么简单,一起来看怎么做 步骤①:…...
数据结构(Java实现)-栈和队列
栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。 先进后出 栈的使用 栈的模拟实现 上述的主要代码 public class MyStack {private int[] elem;private int usedSize;public MyStack() {this.elem new int[5];}Overridepublic …...
毕业季如何做好IT技术面试
在IT技术面试过程中,面试者需要展示多个方面的能力和素质,以确保其能够成功地适应公司的文化和环境,并为公司的发展做出贡献。本文将详细介绍IT技术面试的各个方面,并给出建议和指导。 简历和求职信 简历和求职信是面试官了解面…...
springcloud3 GateWay章节-Nacos+gateway(跨域,filter过滤等5
一 常用工具类 1.1 结构 1.2 跨域 Configuration public class CorsConfig {Beanpublic CorsWebFilter corsFilter() {CorsConfiguration config new CorsConfiguration();config.addAllowedMethod("*");config.addAllowedOrigin("*");config.addAllowe…...
未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?
编辑:陈萍萍的公主一点人工一点智能 未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战,在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...
在软件开发中正确使用MySQL日期时间类型的深度解析
在日常软件开发场景中,时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志,到供应链系统的物流节点时间戳,时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库,其日期时间类型的…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序
一、开发准备 环境搭建: 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 项目创建: File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...
Ascend NPU上适配Step-Audio模型
1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统,支持多语言对话(如 中文,英文,日语),语音情感(如 开心,悲伤)&#x…...
12.找到字符串中所有字母异位词
🧠 题目解析 题目描述: 给定两个字符串 s 和 p,找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义: 若两个字符串包含的字符种类和出现次数完全相同,顺序无所谓,则互为…...
CMake 从 GitHub 下载第三方库并使用
有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...
今日科技热点速览
🔥 今日科技热点速览 🎮 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售,主打更强图形性能与沉浸式体验,支持多模态交互,受到全球玩家热捧 。 🤖 人工智能持续突破 DeepSeek-R1&…...
自然语言处理——循环神经网络
自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元(GRU)长短期记忆神经网络(LSTM)…...
有限自动机到正规文法转换器v1.0
1 项目简介 这是一个功能强大的有限自动机(Finite Automaton, FA)到正规文法(Regular Grammar)转换器,它配备了一个直观且完整的图形用户界面,使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...
初学 pytest 记录
安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...
