最大子数组和
🟡 中等题目描述
给你一个整数数组 nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例 1
输入：nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
输出：6
解释：连续子数组 [4, -1, 2, 1] 的和最大，为 6示例 2
输入：nums = [1]
输出：1
解释：连续子数组 [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 个标签)
动态规划 O(n)
思路
定义 dp[i] 表示以 nums[i] 结尾的最大子数组和。状态转移方程：
dp[i] = max(nums[i], dp[i-1] + nums[i])
即要么从当前元素重新开始，要么延续之前的子数组。
代码实现
/**
* @param {number[]} nums
* @return {number}
*/
function maxSubArray(nums) {
const n = nums.length;
const dp = new Array(n);
dp[0] = nums[0];
let maxSum = dp[0];
for (let i = 1; i < n; i++) {
dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
maxSum = Math.max(maxSum, dp[i]);
}
return maxSum;
}复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(n)
解法二
参考答案 (2 个标签)
Kadane算法 O(1)空间
思路
由于 dp[i] 只依赖于 dp[i-1]，可以用一个变量代替数组。
代码实现
/**
* @param {number[]} nums
* @return {number}
*/
function maxSubArray(nums) {
let currentSum = nums[0];
let maxSum = nums[0];
for (let i = 1; i < nums.length; i++) {
currentSum = Math.max(nums[i], currentSum + nums[i]);
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(1)
图解
nums: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
current: [-2, 1, -2, 4, 3, 5, 6, 1, 5]
maxSum: [-2, 1, 1, 4, 4, 5, 6, 6, 6]