123. Best Time to Buy and Sell Stock III - jiejackyzhang/leetcode-note GitHub Wiki

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

##Approach 1: Dynamic Progrmming，可扩展至k transactions 令dp[i,j]表示max profit up until prices[j] (Note: NOT ending with prices[j]) using at most k transactions. 则：

dp[i,j] = max(dp[i,j-1], prices[j] - prices[t] + dp[i-1,t] {t in [0,j-1]}) //若卖prices[j]，则在之前某个t时刻买了prices[t]
        = max(dp[i,j-1], prices[j] + max(dp[i-1,t] - prices[t]))

base cases为

dp[0,j] = 0 //没有交易
dp[i,0] = 0 //数组长度为1

public class Solution {
    public int maxProfit(int[] prices) {
        if(prices == null || prices.length <= 1) return 0;
        int K = 2;
        int n = prices.length;
        int[][] dp = new int[K+1][n];
        for(int i = 1; i <= K; i++) {
            int tmpMax = dp[i-1][0] - prices[0];
            for(int j = 1; j < n; j++) {
                dp[i][j] = Math.max(dp[i][j-1], prices[j] + tmpMax);
                tmpMax = Math.max(tmpMax, dp[i-1][j] - prices[j]);
            }
        }
        return dp[K][n-1];
    }
}

##Approach 2 维护4个变量，分别表示

• firstBuy: 第一次买的price
• afterFirstSell: 第一次卖后的profit
• afterSecondBuy: 第二次买后的profit
• afterSecondSell: 第二次卖后的profit

public class Solution {
    public int maxProfit(int[] prices) {
        int firstBuy = Integer.MAX_VALUE;
        int afterFirstSell = 0;
        int afterSecondBuy = Integer.MIN_VALUE;
        int afterSecondSell = 0;
        for(int price : prices) {
            //for buy price ,the lower,the better
            firstBuy = Math.min(firstBuy, price);
            // for sell price ,the higher,the better
            afterFirstSell = Math.max(afterFirstSell, price - firstBuy);
            //the profit left after second buy,the higher,the better
            afterSecondBuy = Math.max(afterSecondBuy, afterFirstSell - price);
            // the profit left after second sell ,the higher,the better 
            afterSecondSell = Math.max(afterSecondSell, afterSecondBuy + price);
        }
        return afterSecondSell;
    }
}