Question

Formatted question description: https://leetcode.ca/all/123.html

123. 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:

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.

Example 2:

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.

Example 3:

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


@tag-array

Algorithm

Define local[i][j] as the maximum profit that can be made at most j transactions on the i-th day and the last transaction sold on the last day, which is the local optimal.

Then we define global[i][j] as the maximum profit that can be performed at most j transactions when the i-th day is reached, which is the global optimal (not neccessarily last transaction sold on the last day). Their recurrence is:

local[i][j] = max(global[i-1][j-1] + max(diff, 0), local[i-1][j] + diff)

global[i][j] = max(local[i][j], global[i-1][j])

The local optimal value is compared to the global optimal one less traded the previous day plus a difference greater than 0, and the local optimal of the previous day plus the difference, whichever is greater, and the global optimal compares the local optimal And the previous day’s global optimal

Code

Java

public class Best_Time_to_Buy_and_Sell_Stock_III {

    public class Solution_cache_intermidiates_optimize {
        public int maxProfit(int[] prices) {

            if (prices == null || prices.length == 0) {
                return 0;
            }

            // 0 to i, max profit
            int[] leftMax = new int[prices.length];

            int tmpMin = prices[0];
            for (int i = 1; i < prices.length; i++) {

                // 1. I sold it the day before, but today I can only buy without selling, so the profit is the same as the previous day
                // 2. Or sell today, buy at the previous lowest price
                leftMax[i] = Math.max(leftMax[i - 1], prices[i] - tmpMin);

                tmpMin = Math.min(tmpMin, prices[i]);
            }

            //  i to end, max profit
            int[] rightMax = new int[prices.length];

            int tmpMax = prices[prices.length - 1];
            for (int i = prices.length - 2; i >= 0; i--) {

                rightMax[i] = Math.max(rightMax[i + 1], tmpMax - prices[i]);

                tmpMax = Math.max(tmpMax, prices[i]);
            }

            int max = 0;
            for (int i = 1; i < prices.length; i++) { // @note: here to ensure valid transaction,
                // i.e. tomorrow I can sell it, and yesterday I bought it

                max = Math.max(max, leftMax[i] + rightMax[i]);
            }

            return max;
        }
    }
}

All Problems

All Solutions