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

《Kadane‘s Algorithm专题：最大和连续子数组》

news 2025/9/14 23:04:28

在这里插入图片描述

🚀 博主介绍：大家好，我是无休居士！一枚任职于一线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 构造最终的子数组并返回。