每日算法 — 使用java实现最大子数组和：动态规划Kadane算法与分治策略

问题背景

最大子数组和问题是算法领域最经典的问题之一。假设你有一组股票每日涨跌数据，想要找出连续哪几天持有能获得最大收益；或者你有一组传感器温度波动记录，需要定位连续异常区间的最大强度。这些场景都可以抽象为：在一个整数数组中，找到一个具有最大和的连续子数组。

该问题由布朗大学的Jay Kadane于1984年提出线性时间解法而闻名，是动态规划思想的典范应用。本文将用Java实现Kadane算法，并进一步讲解分治策略的O(n log n)解法及其背后的递归思想。

问题描述

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

示例

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

核心思路

Kadane算法（动态规划）

定义 dp[i] 为以第 i 个元素结尾的连续子数组的最大和。

状态转移方程：

dp[i] = max(nums[i], dp[i-1] + nums[i])

即：以 i 结尾的最大子数组和，要么只包含 nums[i] 自己（前面的和为负数，拖累整体），要么延续前面的子数组。

空间优化：由于 dp[i] 只依赖 dp[i-1]，可以用一个变量代替整个数组。

分治策略

将数组分为左右两半，最大子数组和可能出现在：
1. 完全位于左半部分
2. 完全位于右半部分
3. 跨越左右两部分的中点

前两种情况递归求解，第三种情况从中点向两边扩展求最大和。

Java完整实现

import java.util.Arrays;

/**
 * 最大子数组和 - Kadane算法与分治策略双重实现
 * 对应力扣第53题
 */
public class MaximumSubarray {

    /**
     * 解法一：Kadane动态规划算法
     * 时间复杂度：O(n)  空间复杂度：O(1)
     */
    public int maxSubArrayKadane(int[] nums) {
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("数组不能为空");
        }

        // currentSum: 以当前元素结尾的最大子数组和
        // maxSum: 全局最大子数组和
        int currentSum = nums[0];
        int maxSum = nums[0];

        for (int i = 1; i < nums.length; i++) {
            // 决策：延续前面的子数组，还是从当前元素重新开始
            // 如果 currentSum < 0，它会拖累 nums[i]，不如重新开始
            currentSum = Math.max(nums[i], currentSum + nums[i]);

            // 更新全局最大值
            maxSum = Math.max(maxSum, currentSum);
        }

        return maxSum;
    }

    /**
     * 解法一扩展：同时返回最大子数组的起止索引
     */
    public Result maxSubArrayWithIndex(int[] nums) {
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("数组不能为空");
        }

        int currentSum = nums[0];
        int maxSum = nums[0];
        int currentStart = 0;  // 当前子数组的起始索引
        int maxStart = 0;      // 最大子数组的起始索引
        int maxEnd = 0;        // 最大子数组的结束索引

        for (int i = 1; i < nums.length; i++) {
            if (currentSum + nums[i] < nums[i]) {
                // 重新开始，更新当前起始位置
                currentSum = nums[i];
                currentStart = i;
            } else {
                // 延续前面的子数组
                currentSum += nums[i];
            }

            if (currentSum > maxSum) {
                maxSum = currentSum;
                maxStart = currentStart;
                maxEnd = i;
            }
        }

        return new Result(maxSum, maxStart, maxEnd);
    }

    /**
     * 结果封装类
     */
    public static class Result {
        public final int sum;
        public final int start;
        public final int end;

        public Result(int sum, int start, int end) {
            this.sum = sum;
            this.start = start;
            this.end = end;
        }

        @Override
        public String toString() {
            return String.format("和=%d, 范围[%d, %d]", sum, start, end);
        }
    }

    /**
     * 解法二：分治策略
     * 时间复杂度：O(n log n)  空间复杂度：O(log n)
     */
    public int maxSubArrayDivideConquer(int[] nums) {
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("数组不能为空");
        }
        return divideConquerHelper(nums, 0, nums.length - 1);
    }

    /**
     * 分治递归辅助函数
     * @return 区间[left, right]内的最大子数组和
     */
    private int divideConquerHelper(int[] nums, int left, int right) {
        // 递归终止条件：只有一个元素
        if (left == right) {
            return nums[left];
        }

        int mid = left + (right - left) / 2;

        // 情况1：最大子数组完全在左半部分
        int leftMax = divideConquerHelper(nums, left, mid);

        // 情况2：最大子数组完全在右半部分
        int rightMax = divideConquerHelper(nums, mid + 1, right);

        // 情况3：最大子数组跨越中点
        int crossMax = maxCrossingSum(nums, left, mid, right);

        // 返回三种情况的最大值
        return Math.max(Math.max(leftMax, rightMax), crossMax);
    }

    /**
     * 计算跨越中点的最大子数组和
     * 从中点向左扩展求最大和，从中点+1向右扩展求最大和，两者相加
     */
    private int maxCrossingSum(int[] nums, int left, int mid, int right) {
        // 从中点向左扩展
        int leftSum = Integer.MIN_VALUE;
        int currentSum = 0;
        for (int i = mid; i >= left; i--) {
            currentSum += nums[i];
            leftSum = Math.max(leftSum, currentSum);
        }

        // 从中点+1向右扩展
        int rightSum = Integer.MIN_VALUE;
        currentSum = 0;
        for (int i = mid + 1; i <= right; i++) {
            currentSum += nums[i];
            rightSum = Math.max(rightSum, currentSum);
        }

        // 跨越中点的最大和 = 左半部分最大后缀和 + 右半部分最大前缀和
        return leftSum + rightSum;
    }

    /**
     * 解法三：前缀和优化
     * 利用前缀和与最小前缀和之差求最大子数组和
     * 时间复杂度：O(n)  空间复杂度：O(n)
     */
    public int maxSubArrayPrefixSum(int[] nums) {
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("数组不能为空");
        }

        int n = nums.length;
        // prefixSum[i]表示nums[0]到nums[i-1]的和
        int[] prefixSum = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }

        int maxSum = nums[0];
        int minPrefix = prefixSum[0];  // 前缀和的最小值

        for (int i = 1; i <= n; i++) {
            // 以i-1结尾的子数组和 = prefixSum[i] - min(prefixSum[0..i-1])
            maxSum = Math.max(maxSum, prefixSum[i] - minPrefix);
            minPrefix = Math.min(minPrefix, prefixSum[i]);
        }

        return maxSum;
    }

    /**
     * 扩展：环形子数组的最大和
     * 数组首尾相连，求最大子数组和
     * 关键洞察：最大和在中间（不跨越边界）或跨越边界（即总和减去最小子数组和）
     */
    public int maxSubarraySumCircular(int[] nums) {
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("数组不能为空");
        }

        // 情况1：不跨越边界，就是普通最大子数组和
        int maxKadane = maxSubArrayKadane(nums);

        // 情况2：跨越边界 = 数组总和 - 最小子数组和
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }

        // 找最小子数组和（将数组取反后用Kadane）
        int[] negated = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            negated[i] = -nums[i];
        }
        int minSubarray = -maxSubArrayKadane(negated);

        // 如果所有元素都是负数，minSubarray == totalSum，此时maxKadane就是答案
        if (minSubarray == totalSum) {
            return maxKadane;
        }

        int maxCircular = totalSum - minSubarray;
        return Math.max(maxKadane, maxCircular);
    }

    /**
     * 扩展：乘积最大子数组
     * 由于负负得正，需要同时追踪最大和最小乘积
     */
    public int maxProductSubarray(int[] nums) {
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("数组不能为空");
        }

        // maxProd: 以当前元素结尾的最大乘积
        // minProd: 以当前元素结尾的最小乘积（负数可能变最大）
        int maxProd = nums[0];
        int minProd = nums[0];
        int result = nums[0];

        for (int i = 1; i < nums.length; i++) {
            int num = nums[i];

            // 当前数为负数时，最大和最小会互换
            if (num < 0) {
                int temp = maxProd;
                maxProd = minProd;
                minProd = temp;
            }

            maxProd = Math.max(num, maxProd * num);
            minProd = Math.min(num, minProd * num);

            result = Math.max(result, maxProd);
        }

        return result;
    }

    /**
     * 扩展：和至少为K的最短子数组（单调队列/前缀和优化）
     * 对应力扣第862题
     */
    public int shortestSubarrayAtLeastK(int[] nums, int k) {
        int n = nums.length;
        long[] prefixSum = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }

        // 使用双端队列维护候选前缀和的索引
        java.util.Deque<Integer> deque = new java.util.ArrayDeque<>();
        int minLength = n + 1;

        for (int i = 0; i <= n; i++) {
            // 当前前缀和 - 队首前缀和 >= k，说明找到满足条件的子数组
            while (!deque.isEmpty() && prefixSum[i] - prefixSum[deque.peekFirst()] >= k) {
                minLength = Math.min(minLength, i - deque.pollFirst());
            }

            // 维护单调递增：如果队尾的前缀和 >= 当前前缀和，弹出队尾
            // 因为当前前缀和更小且索引更大，更可能成为未来最优解的左端点
            while (!deque.isEmpty() && prefixSum[deque.peekLast()] >= prefixSum[i]) {
                deque.pollLast();
            }

            deque.offerLast(i);
        }

        return minLength <= n ? minLength : -1;
    }

    // ============ 测试入口 ============
    public static void main(String[] args) {
        MaximumSubarray solution = new MaximumSubarray();

        int[] test1 = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int[] test2 = {1};
        int[] test3 = {5, 4, -1, 7, 8};
        int[] test4 = {-1, -2, -3, -4};
        int[] test5 = {2, 3, -2, 4};  // 乘积测试
        int[] test6 = {1, -1, 5, -2, 3};  // 环形测试

        System.out.println("===== 最大子数组和测试 =====");

        System.out.println("\n测试1: " + Arrays.toString(test1));
        System.out.println("Kadane算法: " + solution.maxSubArrayKadane(test1));
        System.out.println("带索引结果: " + solution.maxSubArrayWithIndex(test1));
        System.out.println("分治策略: " + solution.maxSubArrayDivideConquer(test1));
        System.out.println("前缀和法: " + solution.maxSubArrayPrefixSum(test1));

        System.out.println("\n测试2 (单元素): " + Arrays.toString(test2));
        System.out.println("Kadane算法: " + solution.maxSubArrayKadane(test2));

        System.out.println("\n测试3 (全正数): " + Arrays.toString(test3));
        System.out.println("Kadane算法: " + solution.maxSubArrayKadane(test3));
        System.out.println("带索引结果: " + solution.maxSubArrayWithIndex(test3));

        System.out.println("\n测试4 (全负数): " + Arrays.toString(test4));
        System.out.println("Kadane算法: " + solution.maxSubArrayKadane(test4));

        // 环形子数组测试
        System.out.println("\n===== 环形子数组最大和 =====");
        System.out.println("数组: " + Arrays.toString(test6));
        System.out.println("环形最大和: " + solution.maxSubarraySumCircular(test6));

        // 乘积最大子数组测试
        System.out.println("\n===== 乘积最大子数组 =====");
        System.out.println("数组: " + Arrays.toString(test5));
        System.out.println("最大乘积: " + solution.maxProductSubarray(test5));

        // 最短子数组测试
        System.out.println("\n===== 和至少为K的最短子数组 =====");
        int[] test7 = {2, -1, 2};
        System.out.println("数组: " + Arrays.toString(test7) + ", K=3");
        System.out.println("最短长度: " + solution.shortestSubarrayAtLeastK(test7, 3));
    }
}

算法执行流程图解

以数组 [-2, 1, -3, 4, -1, 2, 1, -5, 4] 用Kadane算法为例：

索引:  0    1     2      3     4      5      6      7      8
数值: -2    1    -3      4    -1      2      1     -5      4

i=0: currentSum = -2, maxSum = -2
i=1: max(1, -2+1=-1) = 1,  maxSum = max(-2, 1) = 1
i=2: max(-3, 1-3=-2) = -2, maxSum = 1
i=3: max(4, -2+4=2) = 4,   maxSum = 4
i=4: max(-1, 4-1=3) = 3,   maxSum = 4
i=5: max(2, 3+2=5) = 5,    maxSum = 5
i=6: max(1, 5+1=6) = 6,    maxSum = 6  <-- 最大值
i=7: max(-5, 6-5=1) = 1,   maxSum = 6
i=8: max(4, 1+4=5) = 5,    maxSum = 6

最终结果: 6，对应子数组 [4, -1, 2, 1]（索引3到6）

复杂度分析

关键技巧总结

1. Kadane核心洞察：以 i 结尾的最大子数组和，只依赖于以 i-1 结尾的最大子数组和。如果前面的和是负数，就应该”断舍离”重新开始。

2. 分治的跨越处理：跨越中点的最大子数组和不是独立问题，而是”左半部分以中点结尾的最大后缀和”加上”右半部分以中点+1开始的最大前缀和”。

3. 环形问题的转化：环形最大子数组和 = max(普通最大子数组和, 数组总和 – 普通最小子数组和)。注意全负数时的边界处理。

4. 乘积问题的特殊性：由于负负得正，需要同时维护最大和最小两个状态，遇到负数时两者互换。

扩展应用

1. 股票最大收益区间：将每日涨跌视为数组元素，最大子数组和就是最佳持有区间的收益
2. 图像处理：在二维矩阵中寻找最大子矩阵和（需要降维后应用Kadane）
3. 语音识别：从音频特征序列中提取能量最强的连续语音片段
4. 基因组分析：在基因表达数据中定位连续高表达区域