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

Java详解LeetCode 热题 100(13):LeetCode 53：最大子数组和（Maximum Subarray）详解

news 来源：原创 2025/8/13 14:48:07

文章目录

- 1. 题目描述
- 2. 理解题目
- 3. 解题思路
- - 3.1 暴力法
  - - 3.1.1 O(n³) 暴力解法
    - 3.1.2 O(n²) 优化的暴力解法
  - 3.2 分治法
  - 3.3 动态规划（Kadane算法）
  - - 3.3.1 动态规划基本思路
    - 3.3.2 Kadane算法（空间优化版本）
  - 3.4 前缀和方法
- 4. 具体实例解析
- 5. 代码优化与技巧
- - 5.1 处理空数组和边界情况
  - 5.2 优化内存使用
  - 5.3 提前返回与特殊情况处理
- 6. 扩展题目和变种
- - 6.1 找到最大子数组的具体位置
  - 6.2 环形子数组的最大和
  - 6.3 最大子矩阵和
- 7. 实际应用场景
- - 7.1 金融领域
  - 7.2 图像处理
  - 7.3 生物信息学
  - 7.4 时间序列分析
- 8. 面试技巧与注意事项
- - 8.1 多种解法的对比
  - 8.2 常见陷阱与错误
  - 8.3 如何在面试中逐步构建解法
  - 8.4 设计单元测试
- 9. 总结
- - 9.1 解法比较
  - 9.2 关键心得
- 10. 练习题目推荐

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
解释：连续子数组 [5,4,-1,7,8] 的和最大，为 23。

约束条件：

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

2. 理解题目

这个问题要求我们在给定的整数数组中找出一个连续的子数组，使得这个子数组内所有元素的和最大。注意以下几点：

必须是连续的子数组：我们不能跳过中间的元素。例如，在 [-2,1,-3,4] 中，我们不能选择 [-2,4]，因为它不是连续的。
子数组至少包含一个元素：即使所有元素都是负数，我们也必须选择至少一个元素。
我们要找的是最大和：如果有多个子数组具有相同的最大和，任选一个返回即可。

在示例1中：[-2,1,-3,4,-1,2,1,-5,4]，最大和的连续子数组是 [4,-1,2,1]，和为6。虽然我们可以看到数组中有更大的单个元素（如4），但题目要求的是子数组的和最大，而不是子数组中的最大元素。

3. 解题思路

对于最大子数组和问题，有多种解决方法，包括暴力法、分治法、动态规划和前缀和等方法。下面我们会详细介绍每种方法，并分析其时间复杂度和空间复杂度。

3.1 暴力法

暴力法是最直观的解决方案，它枚举所有可能的子数组，计算它们的和，然后找出最大值。

3.1.1 O(n³) 暴力解法

最原始的暴力方法是枚举所有可能的子数组，然后计算每个子数组的和。

算法步骤：

初始化一个变量 maxSum 用于保存最大子数组和，初始值为数组的第一个元素
使用两个嵌套循环来枚举所有可能的子数组的起点和终点
使用第三个循环计算每个子数组的和
如果当前子数组的和大于 maxSum，则更新 maxSum
返回 maxSum

Java 代码实现：

public class Solution {public int maxSubArray(int[] nums) {if (nums == null || nums.length == 0) {return 0;}int maxSum = nums[0]; // 初始化最大和为第一个元素int n = nums.length;// 枚举所有可能的子数组for (int i = 0; i < n; i++) {         // 子数组的起始位置for (int j = i; j < n; j++) {     // 子数组的结束位置int currentSum = 0;// 计算从i到j的子数组和for (int k = i; k <= j; k++) {currentSum += nums[k];}// 更新最大和maxSum = Math.max(maxSum, currentSum);}}return maxSum;}
}

时间复杂度分析：

外层循环执行 n 次
中层循环最多执行 n 次
内层循环最多执行 n 次
总时间复杂度：O(n³)

空间复杂度分析：

只使用了常数额外空间，空间复杂度为 O(1)

3.1.2 O(n²) 优化的暴力解法

上面的暴力方法可以进行优化，去掉最内层的循环。我们可以在计算子数组和时，利用之前计算的结果，而不是每次重新计算。

算法步骤：

初始化一个变量 maxSum 用于保存最大子数组和，初始值为数组的第一个元素
使用两个嵌套循环来枚举所有可能的子数组
对于每个起始位置 i，初始化 currentSum = 0，然后向右扩展子数组
每次将新元素加入子数组时，更新 currentSum 并检查是否需要更新 maxSum
返回 maxSum

Java 代码实现：

public class Solution {public int maxSubArray(int[] nums) {if (nums == null || nums.length == 0) {return 0;}int maxSum = nums[0]; // 初始化最大和为第一个元素int n = nums.length;// 枚举所有可能的子数组for (int i = 0; i < n; i++) {         // 子数组的起始位置int currentSum = 0;  // 从位置i开始的子数组的和for (int j = i; j < n; j++) {     // 子数组的结束位置currentSum += nums[j];  // 将当前元素加入子数组// 更新最大和maxSum = Math.max(maxSum, currentSum);}}return maxSum;}
}

时间复杂度分析：

外层循环执行 n 次
内层循环最多执行 n 次
总时间复杂度：O(n²)

空间复杂度分析：

只使用了常数额外空间，空间复杂度为 O(1)

与 O(n³) 的方法相比，这个优化版本去掉了最内层的循环，通过累加的方式计算子数组的和，从而将时间复杂度降低到了 O(n²)。

3.2 分治法

分治法是"分而治之"的策略，它将问题分解为相似的子问题，解决子问题，然后将子问题的解组合起来。对于最大子数组和问题，我们可以将数组划分为左右两部分，分别求出左半部分的最大子数组和、右半部分的最大子数组和，以及跨越中点的最大子数组和，然后取三者中的最大值。

算法步骤：

将数组分成左右两半
递归地求解左半部分的最大子数组和
递归地求解右半部分的最大子数组和
求解跨越中点的最大子数组和（这部分必须包含中点左侧的元素和中点右侧的元素）
返回上述三个值中的最大值

Java 代码实现：

public class Solution {public int maxSubArray(int[] nums) {if (nums == null || nums.length == 0) {return 0;}return maxSubArrayHelper(nums, 0, nums.length - 1);}private int maxSubArrayHelper(int[] nums, int left, int right) {// 基本情况：只有一个元素if (left == right) {return nums[left];}// 找到数组的中点int mid = left + (right - left) / 2;// 递归计算左半部分的最大子数组和int leftMax = maxSubArrayHelper(nums, left, mid);// 递归计算右半部分的最大子数组和int rightMax = maxSubArrayHelper(nums, mid + 1, right);// 计算跨越中点的最大子数组和int crossMax = maxCrossingSum(nums, left, mid, right);// 返回三者中的最大值return Math.max(Math.max(leftMax, rightMax), crossMax);}private int maxCrossingSum(int[] nums, int left, int mid, int right) {// 计算包含中点左侧的最大子数组和int leftSum = 0;int leftMaxSum = Integer.MIN_VALUE;for (int i = mid; i >= left; i--) {leftSum += nums[i];leftMaxSum = Math.max(leftMaxSum, leftSum);}// 计算包含中点右侧的最大子数组和int rightSum = 0;int rightMaxSum = Integer.MIN_VALUE;for (int i = mid + 1; i <= right; i++) {rightSum += nums[i];rightMaxSum = Math.max(rightMaxSum, rightSum);}// 返回跨越中点的最大子数组和return leftMaxSum + rightMaxSum;}
}

时间复杂度分析：

分治法的时间复杂度可以用递归树来分析
在每一层递归中，我们需要 O(n) 的时间来计算跨越中点的最大子数组和
递归树的高度为 log(n)
总时间复杂度：O(n log n)

空间复杂度分析：

由于递归调用栈的深度为 log(n)，空间复杂度为 O(log n)

3.3 动态规划（Kadane算法）

动态规划是解决最大子数组和问题的最优方法之一，特别是Kadane算法。Kadane算法的关键思想是：对于数组中的每个位置，计算以该位置为结束点的最大子数组和，然后从所有这些最大和中找出最大值。

3.3.1 动态规划基本思路

我们用 dp[i] 表示以第 i 个元素结尾的最大子数组和。那么，对于第 i 个元素，我们有两种选择：

将其加入到前面的子数组中（与前面的最大子数组和相加）
单独作为一个新的子数组的开始

所以，状态转移方程为：

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

最终的最大子数组和就是所有 dp[i] 中的最大值。

算法步骤：

创建一个长度为 n 的 dp 数组，其中 dp[i] 表示以第 i 个元素结尾的最大子数组和
初始化 dp[0] =

文章目录

1. 题目描述

2. 理解题目

3. 解题思路

3.1 暴力法

3.1.1 O(n³) 暴力解法

3.1.2 O(n²) 优化的暴力解法

3.2 分治法

3.3 动态规划（Kadane算法）

3.3.1 动态规划基本思路

相关文章：