《Kadane‘s Algorithm专题:最大和连续子数组》
🚀 博主介绍:大家好,我是无休居士!一枚任职于一线Top3互联网大厂的Java开发工程师! 🚀
🌟 在这里,你将找到通往Java技术大门的钥匙。作为一个爱敲代码技术人,我不仅热衷于探索一些框架源码和算法技巧奥秘,还乐于分享这些宝贵的知识和经验。
💡 无论你是刚刚踏入编程世界的新人,还是希望进一步提升自己的资深开发者,在这里都能找到适合你的内容。我们共同探讨技术难题,一起进步,携手度过互联网行业的每一个挑战。
📣 如果你觉得我的文章对你有帮助,请不要吝啬你的点赞👍分享💕和评论哦! 让我们一起打造一个充满正能量的技术社区吧!
目录标题
- 题目
- 问题分析
- 解决方案步骤
- Java实现代码
- 代码解析
- 复杂度分析
题目
输入一个长度为n的整型数组array,数组中的一个或连续多个整数组成一个子数组,找到一个具有最大和的连续子数组。
- 子数组是连续的,比如[1,3,5,7,9]的子数组有[1,3],[3,5,7]等等,但是[1,3,7]不是子数组
- 如果存在多个最大和的连续子数组,那么返回其中长度最长的,该题数据保证这个最长的只存在一个
- 该题定义的子数组的最小长度为1,不存在为空的子数组,即不存在[]是某个数组的子数组
- 返回的数组不计入空间复杂度计算
要解决这个问题,我们可以使用一种经典的算法,称为Kadane’s Algorithm,用于找到具有最大和的连续子数组。接下来,我们将结合题目的要求来实现这个算法。
问题分析
- 最大和子数组:我们需要遍历数组并维护当前子数组的和,同时更新最大和。
- 长度管理:在更新最大和时,我们需要记录对应的子数组的长度,以确保在出现相同最大和时选择长度最长的子数组。
- 边界条件:需要注意数组至少有一个元素的情况。
解决方案步骤
- 初始化当前和和最大和。
- 遍历数组,更新当前和。
- 如果当前和小于零,重置当前和和长度。
- 在每次更新最大和时,记录当前子数组的长度。
- 返回最大和的子数组及其长度。
Java实现代码
public class Solution {/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** @param array int整型一维数组 * @return int整型一维数组*/public int[] maxSubArray(int[] array) {int n = array.length;if (n == 0) return new int[0]; // 不应该发生,题目假定至少一个元素int maxSum = Integer.MIN_VALUE; // 最大和int currentSum = 0; // 当前和int maxLength = 0; // 最大和子数组的长度int currentLength = 0; // 当前子数组的长度int startIndex = 0; // 记录最大和子数组的起始索引int tempStartIndex = 0; // 记录当前子数组的起始索引for (int i = 0; i < n; i++) {currentSum += array[i];currentLength++;// 更新最大和及其长度if (currentSum > maxSum) {maxSum = currentSum;maxLength = currentLength;startIndex = tempStartIndex;} else if (currentSum == maxSum) {// 如果当前和等于最大和,比较长度if (currentLength > maxLength) {maxLength = currentLength;startIndex = tempStartIndex;}}// 如果当前和小于零,重置if (currentSum < 0) {currentSum = 0;currentLength = 0;tempStartIndex = i + 1; // 更新起始索引}}// 构造结果数组int[] result = new int[maxLength];for (int i = 0; i < maxLength; i++) {result[i] = array[startIndex + i];}return result;}
}
代码解析
-
初始化变量:
maxSum
用于存储最大和,初始值设为Integer.MIN_VALUE
以处理负数情况。currentSum
用于记录当前子数组的和。maxLength
和currentLength
分别用于记录最大和子数组的长度和当前子数组的长度。startIndex
和tempStartIndex
用于追踪子数组的起始位置。
-
遍历数组:
- 对于每个元素,更新
currentSum
和currentLength
。 - 检查当前和是否大于最大和,如果是,更新最大和及其长度。
- 如果当前和小于零,重置当前和和长度,并更新子数组的起始位置。
- 对于每个元素,更新
-
返回结果:
- 根据
startIndex
和maxLength
构造最终的子数组并返回。
- 根据
复杂度分析
- 时间复杂度:(O(n)),只需遍历一次数组。
- 空间复杂度:(O(1))(不计返回的结果数组)。
这种方法既高效又满足题目的所有要求。如果你有任何其他问题或需要进一步的帮助,请告诉我!
乐于分享和输出干货的WXGZG:JavaPersons
相关文章:

《Kadane‘s Algorithm专题:最大和连续子数组》
🚀 博主介绍:大家好,我是无休居士!一枚任职于一线Top3互联网大厂的Java开发工程师! 🚀 🌟 在这里,你将找到通往Java技术大门的钥匙。作为一个爱敲代码技术人,我不仅热衷…...
Vue基础(5)
ref属性 在 Vue2 中,ref是一个特殊的属性,用于在模板中获取对某个 DOM 元素或子组件的引用。通过 ref,我们可以在 JavaScript 代码中直接访问该 DOM 元素或组件实例。 示例: <template><div><input ref"inputField&quo…...

面对复杂的软件需求:5大关键策略!
面对软件需求来源和场景的复杂性,有效地管理和处理需求资料是确保项目成功的关键,能够提高需求理解的准确性,增强团队协作和沟通,降低项目风险,提高开发效率。反之,项目可能面临需求理解不准确、团队沟通不…...

使用Git进行版本控制的最佳实践
文章目录 Git简介基本概念仓库(Repository)提交(Commit)分支(Branching) 常用命令初始化仓库添加文件提交修改查看状态克隆仓库分支操作合并分支推送更改 最佳实践使用有意义的提交信息定期推送至远程仓库使…...
【入门1】顺序结构 - B2025 输出字符菱形
题目描述 用 * 构造一个对角线长 55 个字符,倾斜放置的菱形。 输入格式 没有输入要求。 输出格式 如样例所示。用 * 构成的菱形。 输入输出样例 输入 #1 输出 #1**** ********* <C> : #include<stdio.h>int main() {printf(" *\n ***\n**…...
C#DLL热加载|动态替换
我有一个项目 开始取数据和结束数据部分是一样的,但中间处理数据是根据客户需求来转换的 又要求增加一个客户数据转换 主程序是不能停下来的 所以这个项目转数据转换部分做成插件式 每个客户的数据转换都是一个项目 都是一个DLL 主程序里面定义好接口类或者抽象…...
数据库三大范式
目录 第一范式(1NF) 第二范式(2NF) 第三范式(3NF) Oracle三大范式是数据库设计中的规范化过程,旨在减少数据冗余、提高数据一致性和数据库性能。这三大范式包括第一范式(1NF)、第二范式(2NF)和第三范式(3NF)。 第一范式(1NF) 数据库表的每一列都是不可分割…...

【linux】fdisk磁盘分区管理
介绍 fdisk是一个磁盘分区管理工具,可以用来创建、删除、修改和查看磁盘分区。 fdisk一般都是交互式使用,基础语法: fdisk /dev/sdd。进入交互窗口后,有一些选项,需要了解下: 选项含义n创建新分区p查看磁盘的分区情…...

asp.net core 入口 验证token,但有的接口要跳过验证
asp.net core 入口 验证token,但有的接口要跳过验证 在ASP.NET Core中,你可以使用中间件来验证token,并为特定的接口创建一个属性来标记是否跳过验证。以下是一个简化的例子: 创建一个自定义属性来标记是否跳过验证: public clas…...

[mysql]聚合函数GROUP BY和HAVING的使用和sql查询语句的底层执行逻辑
#GROUP BY的使用 还是先从需求出发,我们现在想求员工表里各个部门的平均工资,最高工资 SELECT department_id,AVG(salary) FROM employees GROUP BY department_id 我们就会知道它会把一样的id分组,没有部门的就会分为一组,我们也可以用其他字段来分组,我们想查询不同jb_id…...

从数据中台到数据飞轮:实现数据驱动的升级之路
从数据中台到数据飞轮:实现数据驱动的升级之路 随着数字化转型的推进,数据已经成为企业最重要的资产之一,企业普遍搭建了数据中台,用于整合、管理和共享数据;然而,近年来,数据中台的风潮逐渐减退…...
小记:SpringBoot中,@Alisa和@ApiModelProperty的区别
在 Spring Boot 中,Alias和ApiModelProperty 这两个注解用于不同的目的。 Alias Alias是一个用于定义别名的注解,通常用于 Bean 属性的别名功能,这样在使用某些框架(如 JPA 或 Jackson)时,可以将一个属性名…...

信捷 PLC C语言 定时器在FC中的使用
传统梯形图的定时器程序写起来简单,本文用C语言写定时器的使用。 定时器在c语言中使用,和普通梯形图中使用的区别之一是既有外部条件,也有内部条件。 1.建全局变量 2.建立FC POU 这个是功能POU程序。 这里的Enable是内部条件 3.调用包含定…...

k8s常用对象简介
Pod Pod 是可以在 Kubernetes 中创建和管理的、最小的可部署的计算单元。 Pod 是一组(一个或多个) 容器; 这些容器共享存储、网络、以及怎样运行这些容器的声明。 Pod 中的内容总是并置(colocated)的并且一同调度&…...

【Kaggle | Pandas】练习2:索引,选择和分配
文章目录 数据总表1、读取列2、读取某列的第几行的值3、第一行数据4、读取列中前10个值5、读取索引标签为1 、 2 、 3 、 5和8的记录6、包含索引标签为0 、1 、10和100的记录的country 、province 、 region_1和region_2列7、 前 100 条记录的country和variety列8、包含Italy葡…...

【flask】 flask redis的使用
目的:如何使用在flask web项目中连接redis,并简单的使用 使用的库包:flask-redis pip install falsk-redis下面的写法是对项目代码进行模块化拆分的写法,在app.py中只进行对象的初始化等操作;exts.py中创建对象&…...
【Unity基础】Unity中的特殊文件夹详解
在Unity项目中,通常可以根据需要创建任意名称的文件夹来组织项目内容,但有一些特定的文件夹名称会触发Unity对其中资源和脚本的特殊处理。这篇文章将详细介绍这些特殊文件夹,帮助开发者在项目中合理地使用它们。 1. Assets 文件夹 Assets文…...

矩阵蠕虫,陈欣出品
第一章 陈欣是一名资深的软件工程师,专门从事分布式系统和人工智能的研究。她的最新项目叫做“MatrixWorm”,目标是创建一个简单而强大的远程控制系统。在这个系统中,控制端可以通过文字命令,让被控制端利用大语言模型的能力来理…...

python 爬虫 入门 五、抓取图片、视频
目录 一、图片、音频 二、下载视频: 一、图片、音频 抓取图片的手法在上一篇python 爬虫 入门 四、线程,进程,协程-CSDN博客里面其实有,就是文章中的图片部分,在那一篇文章,初始代码的28,29行…...
ubantu 编译安装ceph 18.2.4
下载ceph代码 git clone https://github.com/ceph/ceph.git #切换tag git checkout v18.2.4 -b v18.2.4 #下载子模块 会有报错重新执行即可 git submodule update --init --recursive安装ceph所需要的依赖 #curl命令安装 sudo apt install curl#安装ceph依赖 ./install-deps.…...
【Linux】C语言执行shell指令
在C语言中执行Shell指令 在C语言中,有几种方法可以执行Shell指令: 1. 使用system()函数 这是最简单的方法,包含在stdlib.h头文件中: #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...

vscode(仍待补充)
写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh? debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互
引擎版本: 3.8.1 语言: JavaScript/TypeScript、C、Java 环境:Window 参考:Java原生反射机制 您好,我是鹤九日! 回顾 在上篇文章中:CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

ArcGIS Pro制作水平横向图例+多级标注
今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作:ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等(ArcGIS出图图例8大技巧),那这次我们看看ArcGIS Pro如何更加快捷的操作。…...
Spring AI与Spring Modulith核心技术解析
Spring AI核心架构解析 Spring AI(https://spring.io/projects/spring-ai)作为Spring生态中的AI集成框架,其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似,但特别为多语…...

分布式增量爬虫实现方案
之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面,避免重复抓取,以节省资源和时间。 在分布式环境下,增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路:将增量判…...

均衡后的SNRSINR
本文主要摘自参考文献中的前两篇,相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程,其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt 根发送天线, n r n_r nr 根接收天线的 MIMO 系…...

【C++特殊工具与技术】优化内存分配(一):C++中的内存分配
目录 一、C 内存的基本概念 1.1 内存的物理与逻辑结构 1.2 C 程序的内存区域划分 二、栈内存分配 2.1 栈内存的特点 2.2 栈内存分配示例 三、堆内存分配 3.1 new和delete操作符 4.2 内存泄漏与悬空指针问题 4.3 new和delete的重载 四、智能指针…...