面试题63：股票的最大利润

从“后来的最低价不能买过去的最高价”开始

价格按时间为9、11、5、7、16、1、4、2。全数组最低价是1、最高价是16，但1出现在16之后，不能先以1买入再回到过去以16卖出。合法最大利润来自先以5买入、后以16卖出，结果11。

数组顺序代表不可逆的时间顺序。问题“股票的最大利润”本质上是在所有先买后卖的下标对中寻找最大差值，而不是简单求全局最大值减全局最小值。

先预测全递减价格16、11、7、4、2、1的结果。作者期望-1，而不是0：他要求从两个不同时间点完成一次交易，最佳选择是以2买入、以1卖出，承受最小亏损1。

“只能买卖一次”在源码中的真实含义

原章概念“只能买卖一次”容易被理解成“最多一次，可以不交易”。但作者用两个价格4、2期望-2，并对严格递减序列期望-1，证明这里采用的是：恰好完成一次买入和一次卖出。

如果产品允许放弃交易，答案应与0取最大值；那是常见平台变体，不是作者测试定义。两种契约只差初始化和无交易候选，却会在递减输入上产生完全不同的结果。

少于两个价格时不存在合法交易。作者对空输入返回0作为哨兵，但生产接口最好返回optional或错误状态，因为0也可能是两天同价产生的真实利润，单个整数无法区分“无交易可做”和“恰好不赚不亏”。

暴力枚举为何有重复工作

最直接的方法枚举买入日b，再枚举所有更晚卖出日s，比较每个差值。它正确但要检查n乘n量级的价格对，时间O(n平方)、额外空间O(1)。

对一个固定卖出日s，最佳买入价一定是它之前所有价格的最小值；未来卖出日也只需要这个最小值，不关心更贵的历史价格。因此可以把每个前缀压缩成一个。

这就是原章的“维护此前最小价格”与“当前价格减最小价格”。每个卖出日只生成一个最优，再与全局最佳比较。

一次扫描的不变式

扫描到下标i并准备计算当天卖出利润时，minimum必须等于下标0到i-1的最低价格；maxDiff必须等于此前所有合法买卖对的最大差值。这个条件称为。

先用minimum计算当前差值，再把当前价格纳入下一轮最低价，能最直接维持不变式。作者写法等价：循环从i等于2开始，每轮先把numbers[i-1]纳入min，再用numbers[i]卖出；首个交易numbers[1]-numbers[0]已在循环前初始化。

不能先把P_i更新进minimum再计算差值。在允许不交易的版本中，这会产生0并可能看似无害；在作者强制交易版本中，它会让递减序列错误地用“同一天买卖”得到0，覆盖真实的负利润。

忠实还原作者代码

作者以第0天价格初始化min，以第1天减第0天初始化maxDiff。这一步建立了第一个买入日严格早于卖出日的合法交易，也让答案允许为负数。

int MaxDiff(const int* numbers,
            unsigned length) {
    if (numbers == nullptr &&
        length < 2) {
        return 0;
    }
 
    int min = numbers[0];
    int maxDiff = numbers[1] - min;
 
    for (int i = 2;
         i < length;
         ++i) {
        if (numbers[i - 1] < min)
            min = numbers[i - 1];
 
        int currentDiff =
            numbers[i] - min;
        if (currentDiff > maxDiff)
            maxDiff = currentDiff;
    }
 
    return maxDiff;
}

源码入口存在明确逻辑错误：空指针与长度不足使用了逻辑与。只有numbers为空且length小于2时才返回；非空但长度0或1会访问numbers[0]或numbers[1]，空指针但伪造length大于等于2也会解引用空地址。正确保护应在任一条件成立时返回，也就是使用逻辑或。

循环变量是int而length为unsigned，极端长度超过INT_MAX时i自增会溢出；价格差也可能在两个int极值相减时溢出。真实股票价格通常范围有限，但通用库接口应使用size_t遍历并在更宽类型中计算差值。

现代强制交易接口

下面的实现把“无合法交易”与利润0分开，以optional返回；输入价格使用64位整数，并把每一天作为卖出候选后才更新minimum。

#include <algorithm>
#include <cstdint>
#include <optional>
#include <span>
 
std::optional<std::int64_t>
maximalProfit(
    std::span<const std::int64_t> prices) {
    if (prices.size() < 2)
        return std::nullopt;
 
    std::int64_t minimum = prices[0];
    std::int64_t best =
        prices[1] - prices[0];
 
    for (std::size_t i = 1;
         i < prices.size();
         ++i) {
        best = std::max(
            best,
            prices[i] - minimum);
        minimum = std::min(
            minimum,
            prices[i]);
    }
    return best;
}

循环从1开始会再次计算首对差值，但不影响结果，代码顺序更容易读。若64位价格也可能取完整极值，减法仍可能超出64位；可用更宽中间类型或在接口层限制价格范围。

在9、11、5、7、16、1、4、2上，扫描16时此前最低为5，候选利润11刷新best。后来出现1，只能成为未来4和2的买入价，不能反向配对已经过去的16。

允许不交易的变体

若题意是“最多交易一次”，把best初始化为0即可把“不交易”加入候选集合。仍然要维持买入早于卖出的不变式；这不是动态规划状态机所必需的复杂问题，一份前缀最低值已经是最小充分状态。

std::int64_t maxProfitOrSkip(
    std::span<const std::int64_t> prices) {
    if (prices.size() < 2)
        return 0;
 
    std::int64_t minimum = prices[0];
    std::int64_t best = 0;
 
    for (std::size_t i = 1;
         i < prices.size();
         ++i) {
        best = std::max(
            best,
            prices[i] - minimum);
        minimum = std::min(
            minimum,
            prices[i]);
    }
    return best;
}

旧页采用的正是这个语义，并明确让全递减序列收益为0；它本身是常见解法，但与作者Test3和Test7冲突，不能标成原章复刻。多次交易、交易手续费、冷冻期又是其他问题，需要更多状态，不能从这里的单次扫描直接推断。

正确性证明

对任意卖出日s，所有合法买入日都位于0到s-1。minimum保存其中最低价格，因此P_s减minimum不小于同一天卖出时任何其他买入选择的利润，D_s就是该卖出日的最优候选。

全局最优交易必然有某个卖出日s。算法会在扫描到s时生成这个卖出日的最优候选，并把它纳入best；反过来，算法生成的每个候选都由一个更早买入日和当前卖出日组成，是合法交易。因此最终best既不会漏掉最优解，也不会来自非法时序。

时间O(n)，额外空间O(1)。算法只返回利润；若还要买卖下标，应在minimum更新时保存minIndex，在best更新时同时保存当前买入和卖出下标。相同利润的并列策略也要明确，例如优先最早卖出或最短持有期。

返回买卖时刻与并列策略

只返回差值时，相同最低价或相同最大利润选哪一对都不影响答案；一旦接口还返回买卖时刻，比较符号就成为契约。更新最低价时使用严格小于，会保留最早出现的同价买点；使用小于等于，则改为最近的同价买点。更新best时使用严格大于，会保留首个达到最大利润的交易；使用大于等于，会让较晚交易覆盖此前结果。

例如价格2、2、5有两组利润3。若要求最早买入，应保留第0天；若要求最短持有期，应在第二个2出现时更新买点，返回第1天到第2天。再如1、4、1、4有两组最大利润3，优先最早卖出与优先最新交易会返回不同下标。

实现时必须在候选利润刷新best的同一分支中复制minIndex和当前卖出下标，不能循环结束后再根据最终minimum寻找买点，因为最终最低价可能出现在最佳卖出之后。测试也要同时断言利润与下标，才能锁定并列策略；只断言利润无法发现时序信息被后续低价覆盖。

八组官方测试逐项核对

作者Test把MaxDiff结果与expected比较。Test1是普通波动，Test2严格递增，Test3严格递减，Test4全部相等，Test5包含后来的更低价，Test6和Test7是仅有一个合法交易的两元素数组，Test8为空。

最能锁定契约的是Test7：4、2只有一对先买后卖，结果-2。Test3的-1则证明递减序列应选相邻末尾2、1以最小化亏损。Test8只覆盖了错误入口条件恰好为真的组合，没有覆盖保护逻辑的另外两条危险路径。

现代测试除复现官方结果，还应使用O(n平方)暴力法对拍随机短数组。暴力参考要枚举严格满足b小于s的全部下标对，并以首对初始化，不能把0偷偷加入强制交易候选。

#include <array>
#include <cassert>
 
void testMaximalProfit() {
    assert(maximalProfit(
        std::array<std::int64_t, 5>{
            4, 1, 3, 2, 5}) == 4);
    assert(maximalProfit(
        std::array<std::int64_t, 6>{
            16, 11, 7, 4, 2, 1}) == -1);
    assert(maximalProfit(
        std::array<std::int64_t, 2>{
            4, 2}) == -2);
    assert(maximalProfit(
        std::array<std::int64_t, 5>{
            16, 16, 16, 16, 16}) == 0);
    assert(!maximalProfit(
        std::array<std::int64_t, 1>{4}));
    assert(maxProfitOrSkip(
        std::array<std::int64_t, 2>{
            4, 2}) == 0);
}

对拍时还应核对输入未被修改、重复最低价与重复最高价的并列策略，以及极端价格差是否处于所选整数类型范围。

本章练习

本章回顾

1. 股票的最大利润必须尊重时间，买入下标严格早于卖出下标。
2. 作者“只能买卖一次”的源码语义是必须完成一次交易，递减序列返回负数。
3. 对每个卖出日维护此前最小价格，当前价格减最小价格就是该日最佳候选。
4. 以首个合法差值初始化best，才能保留全亏损输入中的最小亏损。
5. 先计算候选再更新最低价，避免同一天买卖和未来低价配过去高价。
6. 作者入口误用逻辑与，正确短数组保护必须使用逻辑或或optional契约。
7. 线性解时间O(n)、空间O(1)，可用O(n平方)暴力枚举独立对拍。
8. 允许不交易、多次交易与作者题目是不同契约，必须分别实现和测试。
9. 作者八组测试中4、2期望-2，是辨别旧页偏差的关键证据。

名词解释