跳到主要内容

最大子数组和

问题​

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

示例：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6

输入：nums = [1]
输出：1

输入：nums = [5,4,-1,7,8]
输出：23

来源：LeetCode 53. 最大子数组和

答案​

方法一：Kadane 算法（推荐）​

核心思路：遍历数组，维护以当前元素结尾的最大子数组和。如果前面的累计和为负，就丢弃，从当前元素重新开始。

maxSubArrayKadane.ts
function maxSubArray(nums: number[]): number {
  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;
}

执行过程演示：

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

i=0: currentSum = -2, maxSum = -2
i=1: currentSum = max(1, -2+1) = max(1, -1) = 1,  maxSum = 1
i=2: currentSum = max(-3, 1-3) = max(-3, -2) = -2, maxSum = 1
i=3: currentSum = max(4, -2+4) = max(4, 2) = 4,    maxSum = 4
i=4: currentSum = max(-1, 4-1) = max(-1, 3) = 3,   maxSum = 4
i=5: currentSum = max(2, 3+2) = max(2, 5) = 5,     maxSum = 5
i=6: currentSum = max(1, 5+1) = max(1, 6) = 6,     maxSum = 6  ✓
i=7: currentSum = max(-5, 6-5) = max(-5, 1) = 1,   maxSum = 6
i=8: currentSum = max(4, 1+4) = max(4, 5) = 5,     maxSum = 6

结果：6（对应子数组 [4, -1, 2, 1]）
复杂度分析
  • 时间复杂度：O(n)O(n) — 一次遍历
  • 空间复杂度：O(1)O(1) — 两个变量
直觉理解

Kadane 算法的核心直觉是："如果前面的累计和拖累了我（为负），我就不要它了，从自己重新开始。"

方法二：动态规划​

更清晰地展示 DP 思路：

maxSubArrayDP.ts
function maxSubArray(nums: number[]): number {
  const n = nums.length;
  // dp[i] 表示以 nums[i] 结尾的最大子数组和
  const dp = new Array(n);
  dp[0] = nums[0];

  for (let i = 1; i < n; i++) {
    dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
  }

  return Math.max(...dp);
}
与 Kadane 的关系

Kadane 算法就是空间优化后的动态规划。currentSum 对应 dp[i]，由于 dp[i] 只依赖 dp[i-1]，所以只需一个变量。

方法三：分治法​

核心思路：将数组分为左右两半，最大子数组要么在左半部，要么在右半部，要么横跨中间。

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

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

  const mid = Math.floor((left + right) / 2);

  // 左半部最大子数组
  const leftMax = divideAndConquer(nums, left, mid);
  // 右半部最大子数组
  const rightMax = divideAndConquer(nums, mid + 1, right);
  // 横跨中间的最大子数组
  const crossMax = maxCrossingSum(nums, left, mid, right);

  return Math.max(leftMax, rightMax, crossMax);
}

function maxCrossingSum(
  nums: number[],
  left: number,
  mid: number,
  right: number
): number {
  // 从 mid 向左扩展
  let leftSum = -Infinity;
  let sum = 0;
  for (let i = mid; i >= left; i--) {
    sum += nums[i];
    leftSum = Math.max(leftSum, sum);
  }

  // 从 mid+1 向右扩展
  let rightSum = -Infinity;
  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) — 不如 Kadane，但展示了分治思想
  • 空间复杂度：O(log⁡n)O(\log n) — 递归栈

方法四：前缀和​

核心思路：最大子数组和 = 最大前缀和 - 最小前缀和。

maxSubArrayPrefix.ts
function maxSubArray(nums: number[]): number {
  let maxSum = -Infinity;
  let prefixSum = 0;
  let minPrefixSum = 0; // 到当前位置之前的最小前缀和

  for (const num of nums) {
    prefixSum += num;
    maxSum = Math.max(maxSum, prefixSum - minPrefixSum);
    minPrefixSum = Math.min(minPrefixSum, prefixSum);
  }

  return maxSum;
}
前缀和思想

如果 prefixSum[j] - prefixSum[i] 最大（j > i），那就是 i+1 到 j 这段子数组的和最大。所以维护遍历过的最小前缀和即可。

这个思路和买卖股票完全一样！对比：

  • 股票：找 prices[j] - prices[i] 的最大值
  • 子数组和：找 prefixSum[j] - prefixSum[i] 的最大值

常见面试追问​

Q1: 如何返回最大子数组本身（不只是和）？​

答案：记录起始和结束索引：

function maxSubArrayWithRange(
  nums: number[]
): { sum: number; start: number; end: number } {
  let currentSum = nums[0];
  let maxSum = nums[0];
  let tempStart = 0;
  let start = 0;
  let end = 0;

  for (let i = 1; i < nums.length; i++) {
    if (nums[i] > currentSum + nums[i]) {
      currentSum = nums[i];
      tempStart = i; // 从当前位置重新开始
    } else {
      currentSum += nums[i];
    }

    if (currentSum > maxSum) {
      maxSum = currentSum;
      start = tempStart;
      end = i;
    }
  }

  return { sum: maxSum, start, end };
}

// 测试
// maxSubArrayWithRange([-2,1,-3,4,-1,2,1,-5,4])
// => { sum: 6, start: 3, end: 6 } → [4,-1,2,1]

Q2: 如果数组是环形的呢？(LeetCode 918)​

答案：最大子数组要么在中间，要么横跨首尾。横跨首尾的最大和 = 总和 - 中间最小子数组和。

function maxSubarraySumCircular(nums: number[]): number {
  let maxSum = -Infinity, minSum = Infinity;
  let curMax = 0, curMin = 0;
  let total = 0;

  for (const num of nums) {
    curMax = Math.max(num, curMax + num);
    maxSum = Math.max(maxSum, curMax);

    curMin = Math.min(num, curMin + num);
    minSum = Math.min(minSum, curMin);

    total += num;
  }

  // 特殊情况：全是负数
  if (total === minSum) return maxSum;

  return Math.max(maxSum, total - minSum);
}

Q3: 如果要求子数组长度至少为 k？​

答案：先计算前 k 个元素的和作为窗口，然后用类 Kadane 的方式扩展：

function maxSubArrayAtLeastK(nums: number[], k: number): number {
  const n = nums.length;

  // 先计算以每个位置结尾的最大子数组和
  const dp = new Array(n);
  dp[0] = nums[0];
  for (let i = 1; i < n; i++) {
    dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
  }

  // 计算前缀和
  let sum = 0;
  for (let i = 0; i < k; i++) sum += nums[i];
  let maxSum = sum;

  for (let i = k; i < n; i++) {
    sum += nums[i] - nums[i - k];
    // 长度恰好为 k 或者更长（加上前面的最优子数组）
    maxSum = Math.max(maxSum, sum, sum + dp[i - k]);
  }

  return maxSum;
}

相关链接​