买卖股票的最佳时机（仅一次交易）。

核心回答

至多进行一次买入和一次卖出，且必须先买后卖。遍历每个卖出日时，最优买入价就是此前出现过的最低价，因此只需维护前缀最低价和最大利润，时间O(n)、额外空间O(1)。如果价格一直下降，选择不交易，利润为0。

Python实现

这里输入是按日期排列的非负整数价格列表；空列表作为边界返回0。本题只处理一次交易；多次交易需要另行定义状态。

def max_profit(prices: list[int]) -> int:
    if len(prices) < 2:
        return 0
    lowest = prices[0]
    best = 0
    for i in range(1, len(prices)):
        price = prices[i]
        best = max(best, price - lowest)
        lowest = min(lowest, price)
    return best

先用旧的lowest计算今天卖出的收益，再把今天纳入最低价，因此买入日期一定在卖出之前。best初始为0，避免所有交易都亏损时返回负数。实现不修改输入，也没有使用切片复制数组。

为什么正确

扫描到第i天之前，lowest是第0至i−1天的最低价格，best是前面已处理卖出日能获得的最大非负利润。若今天卖出，所有合法买入日都在这个前缀中，选择最低价必然最优；把这个候选与best取最大，就覆盖了以今天为卖出日的情况。遍历完便覆盖所有合法卖出日。

例如[7,1,5,3,6,4]：到价格5时此前最低为1，利润4；到价格6时利润更新为5；之后价格4不会改善答案，最终返回5。不能用全数组最大值减最小值而忽略先后，如[7,6,4,3,1]的答案是0。

追问：允许多次交易时如何变化

一次交易只保留“此前最低买入价”，不能把前一次卖出的收益再用于购买。若允许不限次交易、一次最多持有一股且没有手续费或冷冻期，才可累加所有相邻正价差。对于[1,3,2,4]，一次交易最大利润3，不限次可得4；最多两次或k次交易则需要显式管理交易次数，不能沿用同一状态含义。

参考资料