LeetCode刷题之最大子数组

今天打算多做一题。

1、题目描述

在这里插入图片描述

2、逻辑分析

哈哈,这题我前两天在小红书刷到了,博主答不上来,一样的是,我也不知道怎么做。当时只看到评论说什么dp解法,看看题解怎么说。现在才反应过来dp = dynamic programming ,题解给出了两种解题思路:动态规划和分治,先从动态规划开始:
直接代码说明

3、代码演示

public int maxSubArray(int[] nums) {
        // start 变量用于记录以当前遍历到的元素为结尾的子数组的最大和
        int start = 0, maxRes = nums[0];
        // 遍历数组中的每一个元素 x
        for(int x : nums){
            // 对于每一个元素 x,我们有两种选择:  
            // 1. 以 x 开头,形成一个新的子数组(此时子数组和为 x)  
            // 2. 将 x 加入到之前的子数组中(此时子数组和为 pre + x)  
            // 我们选择两者中较大的那个作为当前的最大子数组和 pre 
            start = Math.max(start + x, x);
            // 同时,我们还需要将 pre 与迄今为止找到的最大子数组和 maxAns 进行比较  
            // 如果 pre 更大,那么更新 maxAns 
            maxRes = Math.max(maxRes, start);
        }
        // 返回迄今为止找到的最大子数组和
        return maxRes;
    }

真的是妙极了,简短的代码蕴含了dp思想。时间复杂度;O(n),空间复杂度:O(1)。
start = Math.max(start + x, x);在评论区看到了对这句核心代码的明了阐述如下:
如果前边累加后还不如自己本身大,那就把前边的都扔掉,从此自己本身重新开始累加。
分治算法看不太懂,沉不下心来看,先放放吧,再见啦!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/679492.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【C语言】详解函数(庖丁解牛版)

文章目录 1. 前言2. 函数的概念3.库函数3.1 标准库和头文件3.2 库函数的使用3.2.1 头文件的包含3.2.2 实践 4. 自定义函数4.1 自定义函数的语法形式4.2 函数的举例 5. 形参和实参5.1 实参5.2 形参5.3 实参和形参的关系 6. return 语句6. 总结 1. 前言 一讲到函数这块&#xff…

数据库(19)——字符串函数

函数是指一段可以直接被另一段程序调用的程序代码。 常用的函数 函数功能CONCAT(S1,S2...Sn)字符串拼接LOWER(str)将字符串全部转换为小写UPPER(str)将字符串全部转换为大写LPAD(str,n,pad) 用字符串pad对str的左边进行填充RPAD(str,n,pad)用字符串…

10倍速提升音乐制作,FL Studio21.2.9中文版揭秘!

FL Studio21中文版是数字音频工作站软件领域的一颗璀璨明星,它以强大的功能和直观的操作界面,赢得了音乐制作人和爱好者的广泛青睐。无论是专业音乐人还是初学者,都能通过这款软件探索和实现他们对音乐的创作和想象。本文将详细介绍FL Studio…

Maven实战: 从工程创建自定义archetype

在上一节中(创建自定义archetype)我们手动创建了一个项目模板,经过5步能创建出一个项目模板,如果我有一个现成的项目,想用这个项目作为模板来生成其他项目呢?Maven提供了基于项目生成archetype模板的能力,我们分3步来讲…

公差和配合

配合的选择: 配合特性以及基本偏差的应用: 常用优先配合特性及选用举例 为什么一般情况下选用基孔制而不用基轴制: 优先采用基孔制的原因主要包括工艺性、经济性和标准化: 工艺性。加工孔比加工轴更难,因为孔…

函数计数和跟踪 --- console的count和trace方法

新学到一个小方法,分享一下哦。 使用 console 对象的 trace ⽅法在控制台上输出当前的调用栈,可以追踪⼀个函数的执⾏过程。 当我们想要了解一个函数是如何被其他函数调用的,或者想要查看调用栈中的其他信息时,这个方法非常有用…

韩文图片文字识别,这几款软件轻松驾驭韩语文本

在当今信息爆炸的时代,跨语言交流已成为日常生活和工作中的常态。对于需要处理韩文文本的用户来说,韩文图片文字识别技术无疑是一大福音。今天,就为大家介绍几款优秀的韩文图片文字识别软件,让你轻松驾驭韩语文本,提升…

性能工具之 JMeter 常用组件介绍(二)

文章目录 一、Thread Group二、断言组件1、Response Assertion:响应断言2、Response Assertion:响应断言3、Duration Assertion:响应时间断言4.、JSON Assertion:json断言 一、Thread Group 线程组也叫用户组,是性能测…

【linux根分区扩容】

前言: 今天在安装软件的时候发现我的linux的根分区空间不足了,在网上搜索哈资料解决了。 解决根分区空间不足的问题方法: 第一:用lsblk命令查看 发现还有一些空间不在了。 第二:安装扩容工具: yum inst…

react快速开始(四)-之Vite 还是 (Create React App) CRA? 用Vite创建项目

文章目录 react快速开始(四)-之Vite 还是 (Create React App) CRA? 用Vite创建项目背景Vite 和 (Create React App) CRAVite?Vite 是否支持 TypeScript? 用Vite创建react项目参考 react快速开始(四)-之Vite 还是 (Create React App) CRA? 用Vite创建项…

SpringBoot3依赖管理,自动配置

文章目录 1. 项目新建2. 相关pom依赖3. 依赖管理机制导入 starter 所有相关依赖都会导入进来为什么版本号都不用写?如何自定义版本号第三方的jar包 4. 自动配置机制5. 核心注解 1. 项目新建 直接建Maven项目通过官方提供的Spring Initializr项目创建 2. 相关pom依…

什么是电风扇行情?

“电风扇行情” 是一个金融术语,用于描述证券市场中价格上下波动频繁、幅度较大,但总体趋势不明显的市场状况。   其名称来源于电风扇的扇叶在旋转时,风向不断变化的特征,形象地比喻了市场价格频繁变动但没有明确方向的情景。 …

桥田磁力换模系统|实现模具的自动化快速切换

作为橡塑材料包装及模具专业展会, 历时3天的广州橡塑展在广交会展中心圆满落幕。本次展会桥田智能携桥田快换盘、桥田工业连接器、桥田抓取系统以及新产品桥田MMC磁力换模系统四大产品系列亮相。同时利用动态演示、静态展示以及协作机器人互动等方式,多角度展示了桥…

两种参与茶树O-甲基化儿茶素生物合成的O-甲基转移酶的特征分析-文献精读20

Characterization of two O-methyltransferases involved in the biosynthesis of O-methylated catechins in tea plant 两种参与茶树O-甲基化儿茶素生物合成的O-甲基转移酶的特征分析 茶树三维基因组-文献精读19 比较转录组分析揭示了116种山茶属(Camellia)植物的深层系统…

大模型Chain-of-Thought(CoT)与Agent基础知识与介绍

大模型Chain-of-Thought(CoT)与Agent基础知识与介绍 参考文献:Exploring Equation as a Better Intermediate Meaning Representation for Numerical Reasoning of Large Language Models 仓库:https://github.com/zirui-HIT/Br…

基础篇04——多表查询

多表关系 一对多 多对多 多对多是通过中间表实现的 -- 创建学生表 create table student (id int auto_increment primary key comment ID,name varchar(10) comment 姓名,no varchar(3) comment 学号 ) comment 学生表;insert into student values (null, 黛绮丝, 001),(…

计算机基础(2)——冯诺依曼体系结构

💗计算机基础系列文章💗 👉🍀计算机基础(1)——计算机的发展史🍀👉🍀计算机基础(2)——冯诺依曼体系结构🍀👉&#x1f34…

LeetCode-day02-3067. 在带权树网络中统计可连接服务器对数目

LeetCode-day02-3067. 在带权树网络中统计可连接服务器对数目 题目描述示例示例1:示例2: 思路代码 题目描述 给你一棵无根带权树,树中总共有 n 个节点,分别表示 n 个服务器,服务器从 0 到 n - 1 编号。同时给你一个数组 edges &a…

11 - 员工奖金(高频 SQL 50 题基础版)

11- 员工奖金 -- join和left join的区别 -- 如果是join则右侧的数据有的就插,没的就啥也不干,交白卷,也不留null -- 但是left join让右侧数据在没有对应数据时补上了null select e.name,b.bonus from Employee e left join bonus b on e.empI…

【设计模式】结构型-组合模式

前言 在软件开发中,设计模式是一种被广泛应用的解决问题的方法论。其中,结构性设计模式是一类特别重要的模式,它们用于处理类或对象之间的组合关系,其中之一就是组合模式。组合模式允许客户端统一对待单个对象和对象的组合&#…