题目重点：最多完成一次先买后卖，允许不交易；解释为何不累加所有涨幅，并覆盖递减和相等价格。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练价格为非负整数，买入日严格早于卖出日，最多一次交易；不交易收益0。
- 无手续费、做空或额外仓位限制；空数组或单日返回0。
- 代码只返回利润；若要买卖日和平局选择，须另保存坐标并明确规则。
解题路线
- 把每个交易按卖出日j分类。固定卖出日后最优买价一定是此前日期的最低价格，因此无须枚举所有(i,j)组合。
- 扫描时minimum保存当前日期之前的最低价，best保存之前所有卖出日的最佳非负收益。先用当前price−minimum更新best，再把当前price并入最低价，清楚表达不能同日买卖。
- 最低价可以来自当前最佳交易之后，这不矛盾：它服务未来卖出日，不能倒过来与过去高价配对。只保留历史minimum，天然保证时间方向。
- 正确性归纳：当处理卖出日j时，所有合法买入i<j中最小价格已在minimum；所以本日最优收益完整计算。best再取最大，覆盖所有卖出日及不交易选项。
- 不能累加每次上涨差值，那属于允许多次交易的不同问题。例如[1,4,2,5]，单次最优4，多次累加可得6，本题不能返回6。
- 价格持续下降时所有价差为负，best仍0；不要初始化到第一个负收益然后强制亏损交易。若必须完成一次交易，n<2无解并允许负最佳收益，初始化和返回合同均需改变。
- 调试用枚举所有买卖日作为独立oracle，验证递减、相同价格、多次局部上涨与空输入。不需要用另一份历史最低价实现来相互证明。
手动走一遍
[7,1,5,3,6,4]，卖出价6时此前最低1，最大利润5；[7,6,4,3,1]返回0；[1,4,2,5]返回4，不是多次交易的6。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def max_profit(prices):
if any(type(p) is not int or p < 0 for p in prices):
raise ValueError('expected nonnegative integer prices')
minimum, best = None, 0
for price in prices:
if minimum is not None:
best = max(best, price - minimum)
minimum = price if minimum is None else min(minimum, price)
return best
复杂度
O(n)时间，O(1)工作空间；输入校验额外线性扫描仍是O(n)。若价格为任意精度大整数，比较和减法按位数另计。
易错点与追问
容易失分的边界
- 把最低价与发生在它之前的高价组合。
- 累加上涨差值混成无限次交易。
- 强制交易导致递减数组返回负数。
- 未说明手续费或做空政策。
继续深挖
- 要返回日期，多个同利润怎么选？
- 强制完成一次交易怎样初始化？
- 允许K次交易怎样定义状态？
- 加入手续费或冷却期后需要什么DP？
