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

leecode kadane算法解决数组中子数组的最大和，以及环形数组连续子数组的最大和问题

news 2025/9/6 5:42:32

题目1

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：

输入：nums = [1]
输出：1
示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

kadane算法是什么?

当前元素和加上子数组和小于当前元素的值不如从当前元素开始开启新的子数组 。算法通过一个变量（通常叫currentSum）来记录当前子数组的和，同时用另一个变量（通常叫maxSum）来记录遍历过程中遇到的最大子数组和。


class Solution {public int maxSubArray(int[] nums) {if (nums == null || nums.length == 0) {return 0;}//初值设为头int currentSum = nums[0];int maxSum = nums[0];// 遍历比大小for (int i = 1; i < nums.length; i++) {currentSum = Math.max(nums[i], currentSum + nums[i]);// 更新最大值maxSum = Math.max(maxSum, currentSum);}// 最终得结果return maxSum;}
}

注意上述currentSum记录的是当前子数组和，所以需要不断更新当前的currentSum，maxSum用来记录更新过程中最大和。

上述代码我没可能会有这样的疑问，就是:

currentSum记录的是当前子数组和，需要不断更新当前的currentSum，maxSum用来记录更新过程中最大和。为什么currentSum需要更新，但是还需要maxSum记录最大值，最大值不应该就是最终的currentSum的值吗

那是因为没有认清局部最优解和全局最优解的区别！！！
currentSum就是所遍历的当前数组元素的最大子数组和，但是maxSum是更新整个遍历过程中最大的子数组和。

currentSum 的动态性
currentSum 是动态的，它在每次遍历时都会根据当前元素更新。具体来说，currentSum 的更新规则是：
$c u rre n tS u m = ma x (n u m s [i], c u rre n tS u m + n u m s [i])$

如果 currentSum + nums[i] 大于 nums[i]，说明当前子数组加上新的元素后和更大，继续扩展子数组。
如果 currentSum + nums[i] 小于等于 nums[i]，说明当前子数组加上新的元素后和变小了，不如从 nums[i] 重新开始一个新的子数组。

maxSum 的全局性
maxSum 是全局的，它记录了遍历过程中遇到的最大子数组和。具体来说，maxSum 的更新规则是：
$ma x S u m = ma x (ma x S u m, c u rre n tS u m)$
每次更新 currentSum 后，我们都需要检查 currentSum 是否比 maxSum 更大，如果是，则更新 maxSum。

为什么最大值不一定是最终的 currentSum

在遍历过程中，currentSum 会不断变化，它记录的是以当前元素结尾的最大子数组和。而 maxSum 记录的是遍历过程中遇到的最大子数组和。这两者并不一定相同，原因如下：

currentSum 的局部性：

currentSum 只关注以当前元素结尾的子数组，它是一个局部最优解。
每次更新 currentSum 时，它只考虑当前元素和前一个子数组的和，而不会考虑之前的全局最大值。

maxSum 的全局性：

maxSum 是全局最优解，它记录了遍历过程中遇到的所有局部最优解中的最大值。
通过不断更新 maxSum，这样就不会错过任何可能的最大子数组和。

示例说明

考虑数组 [-2, 1, -3, 4, -1, 2, 1, -5, 4]，分析 currentSum 和 maxSum 的变化：

初始化：
currentSum = -2
maxSum = -2
遍历数组：
i = 1：
currentSum = Math.max(1, -2 + 1) = 1
maxSum = Math.max(-2, 1) = 1
i = 2：
currentSum = Math.max(-3, 1 + -3) = -2
maxSum = Math.max(1, -2) = 1
i = 3：
currentSum = Math.max(4, -2 + 4) = 4
maxSum = Math.max(1, 4) = 4
i = 4：
currentSum = Math.max(-1, 4 + -1) = 3
maxSum = Math.max(4, 3) = 4
i = 5：
currentSum = Math.max(2, 3 + 2) = 5
maxSum = Math.max(4, 5) = 5
i = 6：
currentSum = Math.max(1, 5 + 1) = 6
maxSum = Math.max(5, 6) = 6
i = 7：
currentSum = Math.max(-5, 6 + -5) = 1
maxSum = Math.max(6, 1) = 6
i = 8：
currentSum = Math.max(4, 1 + 4) = 5
maxSum = Math.max(6, 5) = 6
最终结果：
maxSum = 6
总结
currentSum：记录以当前元素结尾的最大子数组和，是一个局部最优解。
maxSum：记录遍历过程中遇到的最大子数组和，是一个全局最优解。

题目2：环形数组求取最大值

**给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空子数组的最大可能和 **。

环形数组意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是 nums[(i + 1) % n] ， nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。

子数组最多只能包含固定缓冲区 nums 中的每个元素一次。形式上，对于子数组 nums[i], nums[i + 1], …, nums[j] ，不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n。

示例 1：

输入：nums = [1,-2,3,-2]
输出：3
解释：从子数组 [3] 得到最大和 3
示例 2：

输入：nums = [5,-3,5]
输出：10
解释：从子数组 [5,5] 得到最大和 5 + 5 = 10
示例 3：

输入：nums = [3,-2,2,-3]
输出：3
解释：从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3

提示：

n == nums.length
1 <= n <= 3 * 104
-3 * 104 <= nums[i] <= 3 * 104

重要结论

对于环形数组（假设该数组头尾相连起来的数组）的话，最大子数组和可能存在两种情况，

1.跨越数组头尾
2没有跨越，就在没连接起来的非环形数组中的子数组

所以求取：

1.非环形状态下数组的总和
2.求非环形数组中的最大子数组
3.求非环形状态下的最小子数组
$环形数组最大子数组和 = 非环形状态下数组的总和 - 非环形状态下的最小子数组$

假设数组的总和为 totalSum，最大子数组和为 maxSubArraySum，最小子数组和为 minSubArraySum。在环形数组中，如果最大子数组和跨越了首尾，那么有以下关系：
$ma x S u b A rr a y S u m = t o t a lS u m - min S u b A rr a y S u m$

疑问：非环形数组中最大子数组和和最小子数组和之间互补吗？环形中呢？

最大子数组和和最小子数组和不是互补的：它们是独立的，但在环形数组中- 存在一种特殊的数学关系。
环形数组的特性：如果最大子数组和跨越了首尾，那么剩下的部分（即最小子数组和）不会跨越首尾。
总和的不变性：通过总和减去最小子数组和，可以得到环形的最大子数组和。

互补关系的误解

在普通数组（非环形）中，最大子数组和和最小子数组和是完全独立的。一个数组可以同时包含一个很大的正子数组和一个很小的负子数组，这两个子数组可以是完全不同的部分，也可以有重叠的部分。因此，它们并不是互补的。

环形数组中的特殊关系

在环形数组中，最大子数组和和最小子数组和之间存在一种特殊的数学关系。这种关系基于以下两个关键点：

环形结构的特性：

如果最大子数组和跨越了数组的首尾，那么剩下的部分（即最小子数组和）不会跨越首尾。
这是因为环形数组的首尾相连，最大子数组和和最小子数组和不可能同时包含同一个元素。

总和的不变性：

数组的总和 totalSum 是固定的。
如果最大子数组和跨越了首尾，那么剩下的部分（即最小子数组和）必须是一个连续的子数组，且不会跨越首尾。

为什么它们不是互补的

尽管在环形数组中，最大子数组和和最小子数组和之间存在上述关系，但它们并不是互补的。互补关系通常意味着两个部分的和等于某个固定的值，例如 A + B = C。然而，在这里，最大子数组和和最小子数组和的关系是基于环形结构的特性，而不是简单的互补关系。
示例
假设数组 nums = [1, -2, 3, -2]，长度 n = 4。
计算总和：
$t o t a lS u m = 1 + (- 2) + 3 + (- 2) = 0$
非环形的最大子数组和：
$n o n C i rc u l a r M a x S u m = 3 (子数组 [3])$
非环形的最小子数组和：
$min S u b A rr a y S u m = - 2 (子数组 [- 2])$
环形的最大子数组和：
$c i rc u l a r M a x S u m = t o t a lS u m - min S u b A rr a y S u m = 0 - (- 2) = 2 (子数组 [1, - 2, 3])$
最终结果：
$res u lt = ma x (n o n C i rc u l a r M a x S u m, c i rc u l a r M a x S u m) = ma x (3, 2) = 3$

当然最大子数组和和最小子数组和在环形数组中数值上不是互补的，两者的和不一定等于总的数组和。

在环形数组中，（前提条件）如果最大子数组和需要跨越数组首尾，那么最大子数组(构成最大子数组和的子数组)与最小子数组(构成最小子数组和的子数组)在位置上是互补的，能够构成完整的环形数组。这是因为环形数组的特性使得最大子数组和和最小子数组和在位置上互不重叠，且覆盖了整个数组。

class Solution {public int maxSubarraySumCircular(int[] nums) {if(nums==null||nums.length==0){return 0;}int totalSum=0;for(int i=0;i<nums.length;i++){totalSum+=nums[i];}int noCircleMaxSum=kadane(nums);int noCircleMinSum=kadaneMin(nums);// 如果最小子数组和等于总和，说明所有元素都是负数，直接返回非环形的最大子数组和if (noCircleMinSum == totalSum) {return noCircleMaxSum;}int circleMaxSum=totalSum-noCircleMinSum;return Math.max(circleMaxSum,noCircleMaxSum);}public int kadane(int []nums){int curSum=nums[0];int maxSum=nums[0];for(int i=1;i<nums.length;i++){curSum=Math.max(nums[i],curSum+nums[i]);maxSum=Math.max(maxSum,curSum);}return maxSum;}public int kadaneMin(int []nums){int curSum=nums[0];int minSum=nums[0];for(int i=1;i<nums.length;i++){curSum=Math.min(nums[i],curSum+nums[i]);minSum=Math.min(minSum,curSum);}return minSum;}
}