53. Maximum Subarray

53. Maximum Subarrayopen in new window

🟠 🔖 数组 分治 动态规划 🔗 LeetCodeopen in new window

题目

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)，使用常数个额外变量。

思路三：分治

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

递归的终止条件：
- 当划分到只有一个元素时，最大子序和就是这个元素本身。
左半部分的最大子序和（递归计算）：
- 递归计算左半部分的最大子序和，即调用 maxSubArray(nums, low, mid)。
右半部分的最大子序和（递归计算）：
- 递归计算右半部分的最大子序和，即调用 maxSubArray(nums, mid+1, high)。
跨越中点的最大子序和：
- 从中点向左、向右分别计算最大子序和，然后相加。
- 从中点向左计算时，从 mid 开始向左累加，取累加和的最大值。
- 从中点向右计算时，从 mid+1 开始向右累加，取累加和的最大值。
返回最大值：
- 最终，取左半部分最大子序和、右半部分最大子序和和跨越中点的最大子序和中的最大值作为整个数组的最大子序和。

时间复杂度：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;
}

53. Maximum Subarray

# 53. Maximum Subarrayopen in new window

# 题目

# 题目大意

# 解题思路

# 思路一：动态规划

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

# 思路三：分治

# 代码

# 相关题目