53. 最大子数组和

题目：最大子数组和

描述：

给定一个整数数组 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's Algorithm）

核心思想是：

1. 用一个变量 currentSum 表示以当前位置结尾的最大连续子数组的和。
2. 用另一个变量 maxSum 记录所有子数组中最大的和。

具体步骤：

• 遍历数组，对于每个位置 i：
  1. 如果 currentSum + nums[i] 的值大于 nums[i]，则说明当前子数组可以继续扩展，将 nums[i] 加入子数组；
  2. 否则，以 nums[i] 为新起点开始一个新的子数组。
• 在每一步，更新 maxSum 为当前最大值。

---

代码实现

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取数组长度
        int n = scanner.nextInt();
        int[] nums = new int[n];

        // 读取数组元素
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }

        Solution solution = new Solution();
        int result = solution.maxSubArray(nums);
        System.out.println(result);

        scanner.close();
    }
}

class Solution {
    public int maxSubArray(int[] nums) {
        // 初始化变量
        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;
    }
}

---

代码解析

示例：nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

1. 初始化：

   • currentSum = -2
   • maxSum = -2

2. 遍历数组：

   • 第 2 个元素 nums[1] = 1：

     • currentSum = max(1, -2 + 1) = 1
     • maxSum = max(-2, 1) = 1

   • 第 3 个元素 nums[2] = -3：

     • currentSum = max(-3, 1 + (-3)) = -2
     • maxSum = max(1, -2) = 1

   • 第 4 个元素 nums[3] = 4：

     • currentSum = max(4, -2 + 4) = 4
     • maxSum = max(1, 4) = 4

   • 第 5 个元素 nums[4] = -1：

     • currentSum = max(-1, 4 + (-1)) = 3
     • maxSum = max(4, 3) = 4

   • 第 6 个元素 nums[5] = 2：

     • currentSum = max(2, 3 + 2) = 5
     • maxSum = max(4, 5) = 5

   • 第 7 个元素 nums[6] = 1：

     • currentSum = max(1, 5 + 1) = 6
     • maxSum = max(5, 6) = 6

   • 第 8 个元素 nums[7] = -5：

     • currentSum = max(-5, 6 + (-5)) = 1
     • maxSum = max(6, 1) = 6

   • 第 9 个元素 nums[8] = 4：

     • currentSum = max(4, 1 + 4) = 5
     • maxSum = max(6, 5) = 6

最终结果：maxSum = 6。

---

时间复杂度

1. 时间复杂度：

   • 遍历数组一次，时间复杂度为 O(n)。

2. 空间复杂度：

   • 只使用了常数级别的额外空间，空间复杂度为 O(1)。

---

总结

• 动态规划中的 Kadane's Algorithm 是解决最大子数组和问题的经典方法。
• 它高效且易于实现，适合处理大规模数据。
• 每一步都动态决定当前子数组是否需要扩展还是重新开始，有助于找到最优解。