30. 最大子序和：找到一个具有最大和的连续子数组（最少包含一个元素）

找到具有最大和的连续子数组是经典的动态规划问题，通常称为“最大子序和”问题。这个问题可以用 Kadane’s Algorithm 高效解决，它的时间复杂度为 O(n)。

1. 问题描述

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

2. Kadane's Algorithm 的算法思路

1. 初始化
   • 使用两个变量：currentSum 和 maxSum。
   • currentSum 用来记录当前子数组的和。
   • maxSum 用来记录遇到过的最大子数组的和。
2. 遍历数组
   • 对于数组中的每个元素 num：
     • 计算 currentSum：它要么是 num 自己（表示从这个元素重新开始新的子数组），要么是 currentSum + num（表示将 num 加入当前子数组）。
     • 更新 maxSum：它是 maxSum 和 currentSum 中的最大值。
3. 返回结果
   • 最终，maxSum 就是所求的最大子序和。

3. 代码实现

public class MaximumSubarray {

    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;
    }

    public static void main(String[] args) {
        MaximumSubarray solution = new MaximumSubarray();
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int result = solution.maxSubArray(nums);
        System.out.println("The maximum subarray sum is: " + result);
    }
}

4. 示例解释

假设输入数组为 {-2, 1, -3, 4, -1, 2, 1, -5, 4}，算法执行过程如下：

• 初始时：
  • currentSum = nums[0] = -2
  • maxSum = nums[0] = -2
• 遍历数组：
  • i = 1: currentSum = max(1, -2 + 1) = 1, maxSum = max(-2, 1) = 1
  • i = 2: currentSum = max(-3, 1 + -3) = -2, maxSum = max(1, -2) = 1
  • i = 3: currentSum = max(4, -2 + 4) = 4, maxSum = max(1, 4) = 4
  • i = 4: currentSum = max(-1, 4 + -1) = 3, maxSum = max(4, 3) = 4
  • i = 5: currentSum = max(2, 3 + 2) = 5, maxSum = max(4, 5) = 5
  • i = 6: currentSum = max(1, 5 + 1) = 6, maxSum = max(5, 6) = 6
  • i = 7: currentSum = max(-5, 6 + -5) = 1, maxSum = max(6, 1) = 6
  • i = 8: currentSum = max(4, 1 + 4) = 5, maxSum = max(6, 5) = 6

最终，maxSum = 6，对应的最大子数组为 [4, -1, 2, 1]。

5. 复杂度分析

• 时间复杂度：O(n)，其中 n 是数组的长度。算法只需要一次遍历数组。
• 空间复杂度：O(1)，只使用了常数级别的额外空间。

6. 总结

Kadane’s Algorithm 提供了一种简单而高效的方法来找到最大子序和。它通过维护当前子数组的和，并在遍历数组的过程中不断更新最大值，最终找出最大的子序和。该算法在处理涉及连续子数组的问题时非常有效。