Best Time to Buy and Sell Stock III

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).

Idea:

使用数组a[k][i]表示在第i天之多进行k笔交易产生的最大利润 则a[k][i] = max(a[k][i-1], a[k-1][j] + price[i]-price[j]) 其中0 < j < i; 即a[k][i] = max(a[k][i-1], price[i] + max(a[k-1][j] -price[j])) 0 < j < i; a[0][i] = 0, 无交易，a[k][0]，无价格

Code:

public static int maxProfit(int [] prices){
    if (prices == null || prices.length <= 1) return 0;
    int len = prices.length;

    int[][] t = new int[3][len];
    for (int i = 1; i <= 2; i++) {
        int tmpMax =  -prices[0];
        for (int j = 1; j < len; j++) {
            t[i][j] = Math.max(t[i][j - 1], prices[j] + tmpMax);
            tmpMax =  Math.max(tmpMax, t[i - 1][j - 1] - prices[j]);
        }
    }
    return t[2][len - 1];
}

Another Solution:

public static int maxProfit(int [] prices){
    int maxProfit1 = 0; 
    int maxProfit2 = 0; 
    int lowestBuyPrice1 = Integer.MAX_VALUE;
    int lowestBuyPrice2 = Integer.MAX_VALUE;

    for(int p:prices){
        maxProfit2 = Math.max(maxProfit2, p-lowestBuyPrice2);
        lowestBuyPrice2 = Math.min(lowestBuyPrice2, p-maxProfit1); // -maxProfit1 to make sure the profit1 is added to the final result maxProfit2;
        maxProfit1 = Math.max(maxProfit1, p-lowestBuyPrice1);
        lowestBuyPrice1 = Math.min(lowestBuyPrice1, p);
    }
    return maxProfit2;
}