最大子数组和、买卖股票的最佳时机怎样做？

简答

最大子数组和：在 [-2, 1, -3, 4, -1, 2, 1, -5, 4] 里找一段连续的数，让和最大，答案是 [4, -1, 2, 1]，和为 6。暴力枚举所有区间是 O(n²)。

线性做法叫 Kadane 算法，思路来自动态规划：设 current 是“以当前元素结尾”的最大子数组和。走到下一个数 x 时只有两种选择，接在前面那段后面，和是 current + x；或者从 x 自己重新开始。前面那段的和如果是负数，接上只会拖后腿，所以 current = Math.max(x, current + x)。答案是遍历过程中 current 出现过的最大值。

买卖股票（只买卖一次）：给每天的价格，求先买后卖的最大利润。如果今天卖出，最好的买入点一定是今天之前的最低价，所以一边走一边记最低价 minPrice，每天算一次 price - minPrice，取最大值。价格一路下跌时利润是 0，表示不交易。

两题都是一次遍历、O(n) 时间、O(1) 空间。要注意最大子数组和的初始值：数组全是负数时，答案是最大的那个负数，所以要用第一个元素初始化，不能从 0 开始。

最大子数组和

看代码时注意 current 和 best 的区别：current 必须以当前元素结尾，best 是到目前为止见过的最好结果。

function maxSubArray(nums) {
  let current = nums[0];
  let best = nums[0];
  for (let i = 1; i < nums.length; i++) {
    // 前面那段的和是负数时，接上只会更小，不如从自己重新开始
    current = Math.max(nums[i], current + nums[i]);
    best = Math.max(best, current);
  }
  return best;
}

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

为什么要单独记一个 best？因为 current 只代表“必须以当前元素结尾”的最优值，最好的那一段可能早就结束了。第一个例子里，走到下标 6 时 current 是 6，再遇到 -5 就降到 1，如果最后只返回 current，就丢掉了 6。

全是负数时为什么不能从 0 开始？如果 best 初始化为 0，[-3, -1, -2] 会返回 0，相当于选了一个空数组，可题目要求子数组至少包含一个元素。用 nums[0] 初始化，答案就是 -1。

空数组返回 undefined，因为 nums[0] 不存在，循环也不执行。题目一般保证至少有一个元素；真要处理空输入，应该在开头显式判断，按业务约定返回 0 或抛错。

买卖股票的最佳时机

maxProfit 只允许买卖一次，看 minPrice 的更新顺序：代码先更新最低价再算利润，相当于允许同一天买入卖出，利润为 0，不影响结果。maxProfitMultiple 是可以买卖任意多次的版本。

function maxProfit(prices) {
  let minPrice = Infinity;
  let profit = 0;
  for (const price of prices) {
    minPrice = Math.min(minPrice, price);
    profit = Math.max(profit, price - minPrice);
  }
  return profit;
}

function maxProfitMultiple(prices) {
  let profit = 0;
  for (let i = 1; i < prices.length; i++) {
    // 可以买卖任意多次：把每一段上涨都吃下来
    if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];
  }
  return profit;
}

console.log(maxProfit([7, 1, 5, 3, 6, 4])); // 5
console.log(maxProfit([7, 6, 4, 3, 1])); // 0
console.log(maxProfit([])); // 0
console.log(maxProfit([3, 3, 3])); // 0
console.log(maxProfitMultiple([7, 1, 5, 3, 6, 4])); // 7
console.log(maxProfitMultiple([1, 2, 3, 4, 5])); // 4

[7, 1, 5, 3, 6, 4] 为什么是 5 而不是 6？最大值 7 出现在最低价 1 之前，不能先卖后买。代码只用“今天之前或今天”的最低价算利润，所以第 1 天买入 1、第 4 天卖出 6，利润 5。

minPrice 为什么初始化成 Infinity？Infinity 比任何有限数都大，第一天的价格一定会把它替换掉，不用单独处理第一个元素。空数组时循环不执行，返回 0。

可以买卖多次时为什么只要把上涨相加？任何一段从低到高的交易，利润都等于中间每天涨幅的和，比如 1 买 5 卖等于 1→5 这一天的涨幅；把所有上涨的日子都算上、下跌的日子都跳过，就是能拿到的最大利润。[1, 2, 3, 4, 5] 一次买卖是 4，每天买卖加起来也是 4。

两题和动态规划的关系

Kadane 算法本来就是动态规划：状态 dp[i] 是以第 i 个元素结尾的最大和，转移是 dp[i] = max(nums[i], dp[i-1] + nums[i])。因为 dp[i] 只依赖 dp[i-1]，数组压缩成一个变量，空间从 O(n) 变成 O(1)。这种写法在《动态规划怎么入门？爬楼梯和最长递增子序列怎样做？》里的爬楼梯也出现过。

股票题加上“最多交易 k 次”“卖出后要冷冻一天”“每笔交易有手续费”等条件后，就需要显式的状态，比如“今天结束时手里有股票 / 没有股票”两种状态分别的最大收益。

常见追问

最大子数组和还要返回区间的起止位置怎么办？

在 current 选择“从自己重新开始”时，记下当前下标作为临时起点；每次 best 被更新时，把临时起点和当前下标保存为答案区间。时间复杂度不变。

有没有分治的做法？

有。把数组从中间切开，最大子数组要么完全在左半边，要么完全在右半边，要么跨过中点。前两种递归求，跨中点的从中点往两边扫一遍就能求出，整体 O(n log n)，比 Kadane 慢，面试里一般作为思路补充。