• 當(dāng)-1天0持股時(shí)，利潤(rùn)是0。當(dāng)-1天1持股時(shí)，不可能，定義為負(fù)無(wú)窮。
• 當(dāng)i天0交易0持股時(shí)，利潤(rùn)是0。當(dāng)i天0交易1持股時(shí)，不可能，定義為負(fù)無(wú)窮。
• 當(dāng)i天要變成0持股（清倉(cāng)）時(shí)，可以休停保持i-1天持股，也可以賣(mài)出獲得今日股價(jià)price。取較大值。
• 當(dāng)i天要變成1持股（買(mǎi)進(jìn)）時(shí)，可以休停保持i-1天持股，也可以買(mǎi)進(jìn)減去今日股價(jià)price。取較大值。

所以最后的最大利潤(rùn)，就是循環(huán)所有股價(jià)之后，最后的清倉(cāng)利潤(rùn)T[n-1][k][0]

2. 應(yīng)用范例

以上的六個(gè)問(wèn)題都可以歸作k值不同。cooldown冷卻期和transaction fee交易費(fèi)的問(wèn)題也是加上附加條件。

例1：k=1 (easy)

只能交易一次，求最大利潤(rùn)。

遞推公式變?yōu)椋?/p>

T[i][1][0] = max(T[i-1][1][0], T[i-1][1][1] + prices[i])
T[i][1][1] = max(T[i-1][1][1], T[i-1][0][0] - prices[i]) = max(T[i-1][1][1], -prices[i])

這里利用了初始條件：T[i-1][0][0]等于0。
時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)。

public int maxProfit(int[] prices) {
    int T_i10 = 0, T_i11 = Integer.MIN_VALUE;
        
    for (int price : prices) {
        T_i10 = Math.max(T_i10, T_i11 + price);
        T_i11 = Math.max(T_i11, -price);
    }
        
    return T_i10;
}

例2：k=+Infinity (easy)

不限交易次數(shù)，求最大利潤(rùn)。

遞推公式變?yōu)椋?/p>

T[i][k][0] = max(T[i-1][k][0], T[i-1][k][1] + prices[i])
T[i][k][1] = max(T[i-1][k][1], T[i-1][k-1][0] - prices[i]) = max(T[i-1][k][1], T[i-1][k][0] - prices[i])

這里利用了T[i-1][k-1][0] = T[i-1][k][0]
時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)。

public int maxProfit(int[] prices) {
    int T_ik0 = 0, T_ik1 = Integer.MIN_VALUE;
    
    for (int price : prices) {
        int T_ik0_old = T_ik0;
        T_ik0 = Math.max(T_ik0, T_ik1 + price);
        T_ik1 = Math.max(T_ik1, T_ik0_old - price);
    }
    
    return T_ik0;
}

例3：k=2 (hard)

交易次數(shù)為2，求最大利潤(rùn)。

跟例1同理。
遞推公式變?yōu)椋?/p>

T[i][2][0] = max(T[i-1][2][0], T[i-1][2][1] + prices[i])
T[i][2][1] = max(T[i-1][2][1], T[i-1][1][0] - prices[i])
T[i][1][0] = max(T[i-1][1][0], T[i-1][1][1] + prices[i])
T[i][1][1] = max(T[i-1][1][1], -prices[i])

這里利用了初始條件：T[i-1][0][0]等于0。
時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)。

public int maxProfit(int[] prices) {
    int T_i10 = 0, T_i11 = Integer.MIN_VALUE,
        T_i20 = 0, T_i21 = Integer.MIN_VALUE;
        
    for (int price : prices) {
        T_i20 = Math.max(T_i20, T_i21 + price);
        T_i21 = Math.max(T_i21, T_i10 - price);
        T_i10 = Math.max(T_i10, T_i11 + price);
        T_i11 = Math.max(T_i11, -price);
    }
        
    return T_i20;
}

例4：k is arbitrary k是任意輸入值 (hard)

交易次數(shù)k為不定值，求最大利潤(rùn)。

這題是一般情況。重點(diǎn)在于先優(yōu)化一下k的值。
完成任何一次交易都需要一天買(mǎi)入一天賣(mài)出，總共2天。
所以一個(gè)prices數(shù)組最多交易次數(shù)為n/2次。
如果k>=n/2，可以等同于k=無(wú)窮，和例2一樣。
所以先看如果k>=n/2，就用例2方法，如果不，就用一般方法循環(huán)k。如果不優(yōu)化就會(huì)出現(xiàn)TLE時(shí)間限制錯(cuò)誤。
時(shí)間復(fù)雜度O(kn)，空間復(fù)雜度O(k)。

public int maxProfit(int k, int[] prices) {
    if (k >= prices.length >>> 1) {
        int T_ik0 = 0, T_ik1 = Integer.MIN_VALUE;
    
        for (int price : prices) {
            int T_ik0_old = T_ik0;
            T_ik0 = Math.max(T_ik0, T_ik1 + price);
            T_ik1 = Math.max(T_ik1, T_ik0_old - price);
        }
    
        return T_ik0;
    }
        
    int[] T_ik0 = new int[k + 1];
    int[] T_ik1 = new int[k + 1];
    Arrays.fill(T_ik1, Integer.MIN_VALUE);
        
    for (int price : prices) {
        for (int j = k; j > 0; j--) {
            T_ik0[j] = Math.max(T_ik0[j], T_ik1[j] + price);
            T_ik1[j] = Math.max(T_ik1[j], T_ik0[j - 1] - price);
        }
    }
        
    return T_ik0[k];
}

例5：k = +Infinity but with cooldown有冷卻期 (medium)

交易次數(shù)k不限，但不能連續(xù)2天交易（賣(mài)完隔一天才能買(mǎi)），求最大利潤(rùn)。

所以遞歸公式由如下：

T[i][k][0] = max(T[i-1][k][0], T[i-1][k][1] + prices[i])
T[i][k][1] = max(T[i-1][k][1], T[i-1][k][0] - prices[i])

變成 i-2：

T[i][k][0] = max(T[i-1][k][0], T[i-1][k][1] + prices[i])
T[i][k][1] = max(T[i-1][k][1], T[i-2][k][0] - prices[i])

時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)。

public int maxProfit(int[] prices) {
    int T_ik0_pre = 0, T_ik0 = 0, T_ik1 = Integer.MIN_VALUE;
    
    for (int price : prices) {
        int T_ik0_old = T_ik0;
        T_ik0 = Math.max(T_ik0, T_ik1 + price);
        T_ik1 = Math.max(T_ik1, T_ik0_pre - price);
        T_ik0_pre = T_ik0_old;
    }
    
    return T_ik0;
}

例6：k = +Infinity but with transaction fee有交易費(fèi) (medium)

交易次數(shù)k不限，但每次交易有交易費(fèi)fee，求最大利潤(rùn)。

所以遞歸公式由如下：

T[i][k][0] = max(T[i-1][k][0], T[i-1][k][1] + prices[i])
T[i][k][1] = max(T[i-1][k][1], T[i-1][k][0] - prices[i])

變成 i-2：

T[i][k][0] = max(T[i-1][k][0], T[i-1][k][1] + prices[i])
T[i][k][1] = max(T[i-1][k][1], T[i-1][k][0] - prices[i] - fee)
or
T[i][k][0] = max(T[i-1][k][0], T[i-1][k][1] + prices[i] - fee)
T[i][k][1] = max(T[i-1][k][1], T[i-1][k][0] - prices[i])

注意有可能integer溢出
時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)。

解法1：買(mǎi)入時(shí)收費(fèi)

public int maxProfit(int[] prices, int fee) {
    int T_ik0 = 0, T_ik1 = Integer.MIN_VALUE;
    
    for (int price : prices) {
        int T_ik0_old = T_ik0;
        T_ik0 = Math.max(T_ik0, T_ik1 + price);
        T_ik1 = Math.max(T_ik1, T_ik0_old - price - fee);
    }
        
    return T_ik0;
}

解法2：賣(mài)出時(shí)收費(fèi)（long替換int防止溢出錯(cuò)誤）

public int maxProfit(int[] prices, int fee) {
    long T_ik0 = 0, T_ik1 = Integer.MIN_VALUE;
    
    for (int price : prices) {
        long T_ik0_old = T_ik0;
        T_ik0 = Math.max(T_ik0, T_ik1 + price - fee);
        T_ik1 = Math.max(T_ik1, T_ik0_old - price);
    }
        
    return (int)T_ik0;
}

總結(jié)

例4是一般情況的解法，時(shí)間復(fù)雜度O(kn)，空間復(fù)雜度O(k)?？梢?jiàn)交易最大利潤(rùn)取決于：
第i天的操作，最大交易次數(shù)限制k和最后我們手中股票數(shù)額。
例5、例6有一些附加條件不過(guò)也是之前的變形。
希望有所幫助，happy coding！