53. 最大子数组和

🟠   🔖  数组 分治 动态规划  🔗 力扣 LeetCode

题目

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]

Output: 6

Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Example 2:

Input: nums = [1]

Output: 1

Explanation: The subarray [1] has the largest sum 1.

Example 3:

Input: nums = [5,4,-1,7,8]

Output: 23

Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

Constraints:

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

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

题目大意

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

子数组 是数组中的一个连续部分。

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

解题思路

思路一：动态规划

• 设 dp[i] 表示以第 i 个元素结尾的最大子序和
• 状态转移方程为：dp[i] = max(dp[i-1] + nums[i], nums[i])
  • 如果 dp[i-1] 为正数，表示前面的子序和对当前元素有积极的贡献，可以继续累加；
  • 如果 dp[i-1] 为负数，表示前面的子序和对当前元素无积极的贡献，因此当前元素成为新的起点。
• 最终，最大子序和即为所有 dp[i] 中的最大值。

复杂度分析

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

• 空间复杂度：O(n)，使用长度为 n 的数组记录子问题状态。

---

思路二：压缩状态的动态规划

注意到 dp[i] 仅仅和 dp[i-1] 的状态有关，那么可以进行状态压缩，进一步优化空间复杂度：

• 用 pre 和 cur 分别表示以第 i - 1 个和第 i 个元素结尾的最大子序和；用 res 表示最终求得的最大值；
• 状态转移方程为：cur = max(pre + nums[i], nums[i])
• 并更新 pre 和 res 两个参数：
  • pre = cur;
  • res = Math.max(res, cur);
• 最终，最大子序和即为 res。

复杂度分析

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

• 空间复杂度：O(1)，使用常数个额外变量。

---

思路三：分治

使用分治法解决最大子序和问题，可以将问题划分为三个部分：左半部分的最大子序和、右半部分的最大子序和以及跨越中点的最大子序和。

1. 递归的终止条件：

   • 当划分到只有一个元素时，最大子序和就是这个元素本身。

2. 左半部分的最大子序和（递归计算）：

   • 递归计算左半部分的最大子序和，即调用 maxSubArray(nums, low, mid)。

3. 右半部分的最大子序和（递归计算）：

   • 递归计算右半部分的最大子序和，即调用 maxSubArray(nums, mid+1, high)。

4. 跨越中点的最大子序和：

   • 从中点向左、向右分别计算最大子序和，然后相加。
   • 从中点向左计算时，从 mid 开始向左累加，取累加和的最大值。
   • 从中点向右计算时，从 mid+1 开始向右累加，取累加和的最大值。

5. 返回最大值：

   • 最终，取左半部分最大子序和、右半部分最大子序和和跨越中点的最大子序和中的最大值作为整个数组的最大子序和。

复杂度分析

• 时间复杂度：O(n log n)，递归调用的次数是对数级别。

• 空间复杂度：O(log n)，递归调用的深度。

代码

动态规划

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
	let dp = new Array(nums.length);
	dp[0] = nums[0];
	for (let i = 1; i < nums.length; i++) {
		dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
	}
	return Math.max(...dp);
};

压缩状态的动态规划

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
	let pre = nums[0];
	let cur = pre;
	let res = pre;
	for (let i = 1; i < nums.length; i++) {
		cur = Math.max(pre + nums[i], nums[i]);
		pre = cur;
		res = Math.max(res, cur);
	}
	return res;
};

分治

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
	if (!nums || nums.length === 0) {
		return 0;
	}

	return divideAndConquer(nums, 0, nums.length - 1);
};

function divideAndConquer(nums, low, high) {
	// 递归终止条件
	if (low === high) {
		return nums[low];
	}

	// 计算中点
	const mid = Math.floor((low + high) / 2);

	// 递归计算左半部分的最大子序和
	const maxLeft = divideAndConquer(nums, low, mid);

	// 递归计算右半部分的最大子序和
	const maxRight = divideAndConquer(nums, mid + 1, high);

	// 计算跨越中点的最大子序和
	const maxCross = maxCrossingSum(nums, low, mid, high);

	// 返回三者中的最大值
	return Math.max(maxLeft, maxRight, maxCross);
}

function maxCrossingSum(nums, low, mid, high) {
	let leftSum = Number.NEGATIVE_INFINITY;
	let sum = 0;

	// 从中点向左计算最大子序和
	for (let i = mid; i >= low; i--) {
		sum += nums[i];
		leftSum = Math.max(leftSum, sum);
	}

	let rightSum = Number.NEGATIVE_INFINITY;
	sum = 0;

	// 从中点向右计算最大子序和
	for (let i = mid + 1; i <= high; i++) {
		sum += nums[i];
		rightSum = Math.max(rightSum, sum);
	}

	// 返回跨越中点的最大子序和
	return leftSum + rightSum;
}

相关题目

题号	标题	题解	标签	难度
121	买卖股票的最佳时机	[✓]	数组 动态规划
152	乘积最大子数组	[✓]	数组 动态规划
697	数组的度		数组 哈希表
978	最长湍流子数组		数组 动态规划 滑动窗口
1746	经过一次操作后的最大子数组和 🔒		数组 动态规划
1749	任意子数组和的绝对值的最大值		数组 动态规划
2272	最大波动的子字符串		数组 动态规划
2302	统计得分小于 K 的子数组数目		数组 二分查找 前缀和 1+
2321	拼接数组的最大分数		数组 动态规划
2496	数组中字符串的最大值		数组 字符串
2600	K 件物品的最大和		贪心 数学
2606	找到最大开销的子字符串		数组 哈希表 字符串 1+
3026	最大好子数组和		数组 哈希表 前缀和