0123. Best Time to Buy and Sell Stock III

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii

Description

You are given an array prices where prices[i] is the price of a given stock on the ith day.

Find the maximum profit you can achieve. You may complete at most two transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example 1:

**Input:** prices = [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:** prices = [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:** prices = [7,6,4,3,1]
**Output:** 0
**Explanation:** In this case, no transaction is done, i.e. max profit = 0.

Example 4:

**Input:** prices = [1]
**Output:** 0

Constraints:

• 1 <= prices.length <= 105

• 0 <= prices[i] <= 105

ac1 divide and conquer

time limit exceeded.

class Solution {
    public int maxProfit(int[] prices) {
        // edge cases
        if (prices == null || prices.length <= 1) return 0;

        // break into 2 parts
        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
            int tmp = max(prices, 0, i) + max(prices, i, prices.length - 1);
            profit = Math.max(profit, tmp);
        }

        return profit;
    }

    private int max(int[] prices, int s, int e) {
        // 1 transaction
        int min = Integer.MAX_VALUE, max = 0;
        for (int i = s; i <= e; i++) {
            min = Math.min(min, prices[i]);
            max = Math.max(max, prices[i] - min);
        }
        return max;
    }
}

ac2: 2 pass

not intuitive

class Solution {
    public int maxProfit(int[] prices) {
        // edge cases
        if (prices == null || prices.length <= 1) return 0;

        int n = prices.length;
        int[] dp = new int[n];
        dp[0] = 0;

        // first pass
        int min = prices[0];
        for (int i = 1; i < n; i++) {
            min = Math.min(min, prices[i]);
            dp[i] = Math.max(dp[i-1], prices[i] - min);
        }

        int max = prices[n-1], res = dp[n-1], secMax = 0;
        // second pass
        for (int i = n - 1; i >= 0; i--) {
            max = Math.max(max, prices[i]);
            secMax = Math.max(secMax, max - prices[i]);
            dp[i] += secMax;
            res = Math.max(res, dp[i]);
        }

        // result
        return res;
    }
}

/*
2 pass, l -> r and r -> l
*/

ac3:

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/discuss/135704/Detail-explanation-of-DP-solution

// This is intuitive
public int MaxProfitDpCompact1(int[] prices) {
    if (prices.Length == 0) return 0;
    var dp = new int[3, prices.Length];
    for (int k = 1; k <= 2; k++) {
        int min = prices[0];
        for (int i = 1; i < prices.Length; i++) {
            min = Math.Min(min, prices[i] - dp[k-1, i-1]);
            dp[k, i] = Math.Max(dp[k, i-1], prices[i] - min);
        }
    }

    return dp[2, prices.Length - 1];
}

// After some math optimization, we got this:
public int MaxProfitDpCompactFinal(int[] prices)  {
    int buy1 = int.MaxValue, buy2 = int.MaxValue;
    int sell1 = 0, sell2 = 0;

    for (int i = 0; i < prices.Length; i++) {
        buy1 = Math.Min(buy1, prices[i]);
        sell1 = Math.Max(sell1, prices[i] - buy1);
        buy2 = Math.Min(buy2, prices[i] - sell1);
        sell2 = Math.Max(sell2, prices[i] - buy2);
    }

    return sell2;
}