跳到主要内容

53. 最大子数组和

题目描述​

给你一个整数数组 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

提示：

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104

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

出处：LeetCode

解法一：动态规划​

思路​

我们可以使用动态规划来解决这个问题。我们可以定义一个一维数组 dp，其中 dp[i] 表示以 nums[i] 结尾的连续子数组的最大和。我们可以使用如下的状态转移方程：

  • 当 dp[i-1] > 0 时，dp[i] = dp[i-1] + nums[i]；
  • 当 dp[i-1] ≤ 0 时，dp[i] = nums[i]。
  • 初始状态为 dp[0] = nums[0]。
  • 最终的结果为 max(dp)。

代码​

function maxSubArray(nums: number[]): number {
  const n = nums.length;
  const dp = new Array(n).fill(0);
  dp[0] = nums[0];
  let res = dp[0];
  for (let i = 1; i < n; i++) {
    dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
    res = Math.max(res, dp[i]);
  }
  return res;
}

复杂度分析​

  • 时间复杂度：O(n)O(n)，其中 nn 是数组 nums 的长度。
  • 空间复杂度：O(n)O(n)。

解法二：分治法​

思路​

我们可以使用分治法来解决这个问题。我们可以将数组 nums 分成两部分，分别求解左半部分的最大子数组和、右半部分的最大子数组和以及跨越中点的最大子数组和。最终的结果为这三个结果的最大值。

我们可以使用递归来实现这个算法。递归函数 helper 的参数为数组 nums、左边界 left 和右边界 right，返回值为以 nums 在区间 [left, right] 中的连续子数组的最大和。递归函数的终止条件为 left === right，此时数组 nums 中只有一个元素，最大和即为这个元素。

在递归函数中，我们可以计算出数组 nums 中间元素的下标 mid，然后递归求解左半部分的最大子数组和 leftSum 和右半部分的最大子数组和 rightSum。接着，我们需要计算跨越中点的最大子数组和 crossSum。我们可以从中点开始向左扩展，计算左半部分的最大和 leftCrossSum，从中点开始向右扩展，计算右半部分的最大和 rightCrossSum，最终的结果为 leftCrossSum + rightCrossSum。

代码​

function maxSubArray(nums: number[]): number {
  return helper(nums, 0, nums.length - 1);
}

function helper(nums: number[], left: number, right: number): number {
  if (left === right) {
    return nums[left];
  }

  const mid = left + Math.floor((right - left) / 2);
  const leftSum = helper(nums, left, mid);
  const rightSum = helper(nums, mid + 1, right);
  const crossSum = crossMaxSubArray(nums, left, right, mid);

  return Math.max(leftSum, rightSum, crossSum);
}

function crossMaxSubArray(nums: number[], left: number, right: number, mid: number): number {
  let leftSum = Number.MIN_SAFE_INTEGER;
  let sum = 0;
  for (let i = mid; i >= left; i--) {
    sum += nums[i];
    leftSum = Math.max(leftSum, sum);
  }

  let rightSum = Number.MIN_SAFE_INTEGER;
  sum = 0;
  for (let i = mid + 1; i <= right; i++) {
    sum += nums[i];
    rightSum = Math.max(rightSum, sum);
  }

  return leftSum + rightSum;
}

复杂度分析​

  • 时间复杂度：O(nlog⁡n)O(n \log n)，其中 nn 是数组 nums 的长度。
  • 空间复杂度：O(log⁡n)O(\log n)。