如何解决买卖股票 II 问题？

核心回答

买卖股票II允许不限次数交易，但任意时刻最多持有一股，且没有手续费、冷冻期。最直接的解法是累加所有相邻两天的正差价：上涨就计入收益，下跌不持有；一次遍历即可，时间复杂度 O(n)，额外空间 O(1)。

例如 [7,1,5,3,6,4] 的正差价是4和3，最大利润为7。连续上涨时，逐日累加与低点买入、最高点卖出的收益相同，并不需要实际每天卖掉再买回来。

为什么这个贪心正确

任意一次从第a天买入、第b天卖出的利润，都能拆成这段时间内的相邻差价之和：

prices[b]-prices[a] = (prices[a+1]-prices[a]) + … + (prices[b]-prices[b-1])。

持仓最多一股意味着任何一个相邻区间最多贡献一次涨跌。无论怎样交易，总利润都不可能超过“所有正差价之和”；而把连续上升区间合并成一次买入卖出，就能恰好得到这份收益。因此它既是上界，也确实可达到。

这里依赖交易次数不限、没有额外交易费用或等待限制。算法是在已知完整价格序列下求最优值，不是预测未来价格的交易策略。

Python实现

def max_profit(prices):
    profit = 0
    for i in range(1, len(prices)):
        gain = prices[i] - prices[i - 1]
        if gain > 0:
            profit += gain
    return profit

从下标1开始，避免把第0天与不存在的前一天比较。单个价格、全相等或持续下跌都返回0；这个实现也自然支持空数组。无需排序，排序会破坏买卖必须遵守的时间顺序。

也可以怎样用动态规划解释

定义处理完当天后的两个状态：cash 是不持股的最大收益，hold 是持有一股时的最大现金余额。买入会扣除股价，卖出会增加股价，因此对当天价格p：

• new_cash = max(cash, hold+p)：继续不持股，或今天卖出。
• new_hold = max(hold, cash-p)：继续持股，或今天买入。

初始化为第一天不买时 cash=0、买入时 hold=-prices[0]；最终返回不持股的 cash。下面保留昨日两个状态计算今日，便于以后加入其他约束：

def max_profit_dp(prices):
    if not prices:
        return 0
    cash, hold = 0, -prices[0]
    for i in range(1, len(prices)):
        price = prices[i]
        next_cash = max(cash, hold + price)
        next_hold = max(hold, cash - price)
        cash, hold = next_cash, next_hold
    return cash

这个版本同样是 O(n) 时间、O(1)额外空间。贪心更短，动态规划则清楚表达了持仓与动作，方便回答变形题。

常见追问

和股票I有什么区别？

股票I只允许一笔交易，需要找先买后卖的最大价差；股票II可在不同上升区间反复交易。比如 [1,3,2,4]，一笔最多赚3，多笔可以赚4。

有手续费或冷冻期，还能直接累加正差价吗？

不能直接套用。手续费会让拆成多笔交易改变成本，冷冻期会限制卖出后的买入时间，需要调整状态转移。比如加入手续费时，可在卖出转移中扣一次费用；加入冷冻期则需增加相应状态或引用更早的不持仓状态。

需要给出具体交易记录怎么办？

在每段上涨开始的低点买入，在该段结束的高点卖出，跳过平价区间即可。只求最大利润时不必保存这些区间，因此可以保持常数额外空间。

参考资料