最大子序和

问题

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

示例：

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

解答

动态规划（Kadane 算法）

/**
 * 最大子序和 - 动态规划
 * @param {number[]} nums
 * @return {number}
 */
function maxSubArray(nums) {
  // dp[i] 表示以 nums[i] 结尾的最大子数组和
  // 状态转移：dp[i] = max(dp[i-1] + nums[i], nums[i])
  // 要么接上前面的子数组，要么从当前位置重新开始
  
  let maxSum = nums[0];    // 全局最大和
  let currentSum = nums[0]; // 以当前元素结尾的最大和
  
  for (let i = 1; i < nums.length; i++) {
    // 如果前面的和是负数，不如从当前元素重新开始
    currentSum = Math.max(currentSum + nums[i], nums[i]);
    // 更新全局最大值
    maxSum = Math.max(maxSum, currentSum);
  }
  
  return maxSum;
}

// 测试
console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // 6
console.log(maxSubArray([1]));                              // 1
console.log(maxSubArray([5, 4, -1, 7, 8]));                 // 23
console.log(maxSubArray([-1]));                             // -1

分治法

/**
 * 最大子序和 - 分治法
 * @param {number[]} nums
 * @return {number}
 */
function maxSubArrayDivide(nums) {
  return divideAndConquer(nums, 0, nums.length - 1);
}

function divideAndConquer(nums, left, right) {
  // 递归终止条件
  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 = crossSum(nums, left, mid, right);
  
  return Math.max(leftMax, rightMax, crossMax);
}

function crossSum(nums, left, mid, right) {
  // 从中点向左扩展的最大和
  let leftSum = -Infinity;
  let sum = 0;
  for (let i = mid; i >= left; i--) {
    sum += nums[i];
    leftSum = Math.max(leftSum, sum);
  }
  
  // 从中点向右扩展的最大和
  let rightSum = -Infinity;
  sum = 0;
  for (let i = mid + 1; i <= right; i++) {
    sum += nums[i];
    rightSum = Math.max(rightSum, sum);
  }
  
  return leftSum + rightSum;
}

// 测试
console.log(maxSubArrayDivide([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // 6

返回子数组的起止位置

/**
 * 最大子序和 - 同时返回起止索引
 * @param {number[]} nums
 * @return {{sum: number, start: number, end: number}}
 */
function maxSubArrayWithIndex(nums) {
  let maxSum = nums[0];
  let currentSum = nums[0];
  
  let start = 0;      // 最大子数组起始位置
  let end = 0;        // 最大子数组结束位置
  let tempStart = 0;  // 当前子数组起始位置
  
  for (let i = 1; i < nums.length; i++) {
    if (currentSum + nums[i] < nums[i]) {
      // 从当前位置重新开始
      currentSum = nums[i];
      tempStart = i;
    } else {
      currentSum = currentSum + nums[i];
    }
    
    if (currentSum > maxSum) {
      maxSum = currentSum;
      start = tempStart;
      end = i;
    }
  }
  
  return { sum: maxSum, start, end };
}

// 测试
const result = maxSubArrayWithIndex([-2, 1, -3, 4, -1, 2, 1, -5, 4]);
console.log(result); // { sum: 6, start: 3, end: 6 }
console.log([-2, 1, -3, 4, -1, 2, 1, -5, 4].slice(result.start, result.end + 1)); // [4, -1, 2, 1]

关键点

• 状态定义：dp[i] 表示以第 i 个元素结尾的最大子数组和
• 状态转移：dp[i] = max(dp[i-1] + nums[i], nums[i])，要么延续前面，要么重新开始
• 空间优化：只需要前一个状态，用一个变量即可，空间复杂度 O(1)
• 时间复杂度：动态规划 O(n)，分治法 O(n log n)
• 边界处理：数组全为负数时，返回最大的那个负数