文章目录
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] =