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 (i.e., you must sell the stock before you buy again).

Example 1:

<code>Input: [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
            Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3./<code>

Example 2:

<code>Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
            Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
            engaging multiple transactions at the same time. You must sell before buying again.
/<code>

Example 3:

<code>Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0./<code>

題目大概意思就是，股票的價格變化如數組中所示，只可以最多兩次交易，找出最大利潤，比如說3,3,5,0,0,3,1,4，如果允許多次交易，可以3買入5賣出，0買入3賣出，1買入4賣出，利潤為2+3+3=8,但是次數只能允許最多兩次交易。

這題需要看一下我上一篇文章Best Time to Buy and Sell Stock II解題，看懂的話其實這個題也很簡單，我們定義二個數組來記錄最大值，第一個數組是一次交易的，第二個數組是兩次交易的，也就是二維數組。比如這個數列3,5,0,3,1,4

T2(3,5,0,3,1,4) = Max{ T2(3,5,0,3,1), 4到能賺錢的地方比如1，3，0，3 + T1(3，5，..)}

T1(3,5,0,3,1,4) = Max{ T1(3,5,0,3,1), 4到能賺錢的地方比如1，3，0，3 }

最後我們比較T1(3,5,0,3,1,4)和T2(3,5,0,3,1,4)中數誰大即可

貼出代碼：

<code>    public static int maxProfit(int[] prices) {

        if(prices.length == 0) return 0;

        int[][] maxProfits = new int[2][prices.length];

        int[] curMaxProfit = new int[2];
        for (int i = 1; i < prices.length; i++) {

            for (int j = i - 1; j >= 0; j--) {
                if(prices[i] > prices[j]) {
                    curMaxProfit[0] = Math.max(curMaxProfit[0], prices[i] - prices[j]);
                    curMaxProfit[1] = Math.max(curMaxProfit[1], prices[i] - prices[j] + (j > 0 ? maxProfits[0][j - 1] : 0));
                }
            }

            maxProfits[1][i] = curMaxProfit[1] > maxProfits[1][i - 1] ? curMaxProfit[1] : maxProfits[1][i - 1];
            maxProfits[0][i] = curMaxProfit[0] > maxProfits[0][i - 1] ? curMaxProfit[0] : maxProfits[0][i - 1];

        }

        return maxProfits[0][prices.length - 1] > maxProfits[1][prices.length - 1] ? maxProfits[0][prices.length - 1] : maxProfits[1][prices.length - 1];
    }/<code>

閱讀更多 v心之所向v 的文章

關鍵字: sell profit length