Kadane 算法

Kadane 算法是一种处理最大子数组和问题的 O(n) 级动态规划算法。核心在于：当前位置最大和要么是当前值，要么是当前值加上前一位置的最大和。

53. 最大子数组和 (Maximum Subarray)

题目描述

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

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

解题思路

动态规划：累积和判断。

1. 思考当前位置 dp[i] 的构成：
   • 如果之前的 dp[i-1] > 0，则 dp[i] = dp[i-1] + nums[i]。
   • 否则 dp[i] = nums[i]（抛弃之前的负数累积）。
2. 可优化空间到 O(1)，仅使用一个变量记录当前和 pre。

Java 代码实现

class Solution {
    public int maxSubArray(int[] nums) {
        int res = nums[0], pre = 0;
        for (int num : nums) {
            pre = Math.max(pre + num, num);
            res = Math.max(res, pre);
        }
        return res;
    }
}

---

918. 环形子数组的最大和 (Maximum Sum Circular Subarray)

题目描述

给定一个长度为 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. 非跨越场景：就是普通 53 题的 maxSum。
2. 跨越场景：即包含头部和尾部。
   • 最大和 = 总和 - 最小连续子数组和。
   • 例外：如果数组全是负数，minSum == totalSum，此时最大和依然是 max(nums)，即 53 题的结果。

Java 代码实现

class Solution {
    public int maxSubArrayCircular(int[] nums) {
        int totalSum = 0, maxSum = nums[0], minSum = nums[0];
        int curMax = 0, curMin = 0;
        for (int x : nums) {
            curMax = Math.max(curMax + x, x);
            maxSum = Math.max(maxSum, curMax);
            curMin = Math.min(curMin + x, x);
            minSum = Math.min(minSum, curMin);
            totalSum += x;
        }
        return maxSum > 0 ? Math.max(maxSum, totalSum - minSum) : maxSum;
    }
}

(注：如果 maxSum < 0 说明数组全是负数，此时 totalSum - minSum 可能为 0，应直接返回 maxSum)。