买卖股票的最佳时机 III 图解题解

买卖股票 III 比前两版多了哪条硬限制

给数组 prices，prices[i] 是第 i 天股价，最多完成两笔交易、任何时刻最多持一股，求最大总利润。它比只买卖一次的 121、无限次的 122 多了「最多两笔」这条卡子。题面 prices=[3,3,5,0,0,3,1,4,2] 答案 6：0 买、3 卖赚 3，再 1 买、4 卖赚 3。

为什么把两笔的买卖点全枚举会算爆

要挑出满足 买1<卖1<买2<卖2 的四个时点，全枚举是 O(n⁴)（大 O 记号，描述规模变大时操作数怎么涨）级别，n 稍大就算不完，还有大量重复子问题。把算过的结果存下来复用，就是动态规划（把『到今天为止、四个里程碑各自能达到的最好利润』记下来直接用）。

buy1、sell1、buy2、sell2 这四个状态各盯着什么

不用枚举哪天买卖，只盯四个里程碑此刻能拿到的最好利润。buy1 是第一次买入后的账面利润，买要掏钱所以是负数（所以 buy1 越接近 0、买得越便宜越好，别被负号唬住），就是到今天最低价取负。sell1 是在 buy1 上今天按价 p 卖出后的最大利润。buy2 是拿第一次卖完的钱再买后的最大利润。sell2 是第二次卖出后的最大利润，就是答案。四态一环扣一环，每个都建在前一个已算好的最优上顺推。

四条转移怎么写，为什么同一轮能用刚算好的前一个

每个状态每天都在两条路里取大：保持昨天的值，或今天就把这一步做掉。写成式子是 buy1=max(buy1,-p)、sell1=max(sell1,buy1+p)、buy2=max(buy2,sell1-p)、sell2=max(sell2,buy2+p)，依次是买一、卖一、再买二、卖二。

更新次序不能乱：同一天先更 buy1，sell1 就用刚更的 buy1，buy2 用刚更的 sell1，sell2 用刚更的 buy2。每个状态只依赖前一个的当前值，整张表压成四个变量滚着用，这叫滚动（只留当前值、就地覆盖），空间 O(1)。

拿题面这九天的股价亲手滚一遍四态

prices=[3,3,5,0,0,3,1,4,2]，初值 buy1=buy2=负无穷、sell1=sell2=0。第 0 天价 3：buy1=-3、buy2=-3（buy2 此刻只是占位、还没真第二次买）、sell1=sell2=0。第 2 天价 5：sell1=max(0,-3+5)=2、sell2=2。第 3 天价 0：buy1=0、buy2=max(-3,2-0)=2。第 5 天价 3：sell1=3、sell2=max(2,2+3)=5。第 7 天价 4：sell1=4、sell2=max(5,2+4)=6。其余各天四态不变。最后 sell2=6，正是题面答案。

buy 初值写成 0，利润为什么会凭空虚高

扫一遍 prices、每天四次取大，时间 O(n)；只用四个变量滚动，空间 O(1)。buy1、buy2 初值写成 0 是最常见的错，那等于没花钱就凭空持股、利润偏高，得设成负无穷；sell1、sell2 才初值 0。顺序也不能乱，sell1 挪到 buy1 前面就会读到没更新的旧 buy1，链当场断。

Python

def maxProfit(prices):
    buy1 = buy2 = float("-inf")
    sell1 = sell2 = 0
    for p in prices:
        buy1 = max(buy1, -p)
        sell1 = max(sell1, buy1 + p)
        buy2 = max(buy2, sell1 - p)
        sell2 = max(sell2, buy2 + p)
    return sell2

C++

int maxProfit(vector<int>& prices){
    long buy1 = LONG_MIN, buy2 = LONG_MIN;
    long sell1 = 0, sell2 = 0;
    for(int p : prices){
        buy1 = max(buy1, (long)-p);
        sell1 = max(sell1, buy1 + p);
        buy2 = max(buy2, sell1 - p);
        sell2 = max(sell2, buy2 + p);
    }
    return sell2;
}

Java

int maxProfit(int[] prices){
    int buy1 = Integer.MIN_VALUE, buy2 = Integer.MIN_VALUE;
    int sell1 = 0, sell2 = 0;
    for(int p : prices){
        buy1 = Math.max(buy1, -p);
        sell1 = Math.max(sell1, buy1 + p);
        buy2 = Math.max(buy2, sell1 - p);
        sell2 = Math.max(sell2, buy2 + p);
    }
    return sell2;
}