123. Best Time to Buy and Sell Stock III

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.

Constraints:

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 105

Solution:

dfs

class Solution {
    public int maxProfit(int[] prices) {
       int n = prices.length;

       int result = dfs(n - 1, prices, 0, 2);
       return result;
    }

    private int dfs(int i, int[] prices, int hold, int transCount){
        if (transCount < 0){
            return Integer.MIN_VALUE;
        }

        if (i < 0){
            if (hold == 1){
                return Integer.MIN_VALUE;
            }else{
                return 0;
            }
        }

        if (hold == 1){
            return Math.max(dfs(i - 1, prices, 1, transCount), dfs(i-1, prices, 0, transCount) - prices[i]);
        }
        // 卖出：消耗 1 次交易次数
        return Math.max(dfs(i -1, prices, 0, transCount), dfs(i-1, prices, 1, transCount-1) + prices[i]);
    }
}

// TC: O(2^n)
// SC: O(n)

dfs + memo

class Solution {
    public int maxProfit(int[] prices) {
       int n = prices.length;
       int[][][] memo = new int[n][2][3];
       for (int[][] m : memo){
        for (int[] row: m){
            Arrays.fill(row, -1);
        }
       }
       int result = dfs(n - 1, prices, 0, 2, memo);
       return result;
    }

    private int dfs(int i, int[] prices, int hold, int transCount, int[][][] memo){
        if (transCount < 0){
            return Integer.MIN_VALUE;
        }

        if (i < 0){
            if (hold == 1){
                return Integer.MIN_VALUE;
            }else{
                return 0;
            }
        }

        if (memo[i][hold][transCount] != -1){
            return memo[i][hold][transCount];
        } 

        if (hold == 1){
            return memo[i][hold][transCount] = Math.max(dfs(i - 1, prices, 1, transCount, memo), dfs(i-1, prices, 0, transCount, memo) - prices[i]);
        }
        // 卖出：消耗 1 次交易次数
        return memo[i][hold][transCount] = Math.max(dfs(i -1, prices, 0, transCount, memo), dfs(i-1, prices, 1, transCount-1, memo) + prices[i]);
    }
}

// TC: O(n * 2 * 3)
// SC: O(n)

1:1 translation into a recurrence

class Solution {
    public int maxProfit(int[] prices) {
       int n = prices.length;
       int k = 2;
       int[][][] memo = new int[n+1][2][k + 2];// i j, k
       for (int[][] m : memo){
        for (int[] row: m){
            Arrays.fill(row, Integer.MIN_VALUE/2);
        }
       }
    //    int result = dfs(n - 1, prices, 0, 2, memo);
       for (int j = 1; j < k+2; j++){
        memo[0][0][j] = 0;  
       }

       for (int i = 0; i < n; i++){
        for (int j = 1; j < k + 2; j++){
            memo[i + 1][1][j] = Math.max(memo[i][1][j], memo[i][0][j] - prices[i]);
            memo[i + 1][0][j] = Math.max(memo[i][0][j], memo[i][1][j -1] + prices[i] );
        }
       }

    return memo[n][0][k+1];

    //    return result;
    }

    private int dfs(int i, int[] prices, int hold, int transCount, int[][][] memo){
        if (transCount < 0){
            return Integer.MIN_VALUE;
        }

        if (i < 0){
            if (hold == 1){
                return Integer.MIN_VALUE;
            }else{
                return 0;
            }
        }

        if (memo[i][hold][transCount] != -1){
            return memo[i][hold][transCount];
        } 

        if (hold == 1){
            return memo[i][hold][transCount] = Math.max(dfs(i - 1, prices, 1, transCount, memo), dfs(i-1, prices, 0, transCount, memo) - prices[i]);
        }
        // 卖出：消耗 1 次交易次数
        return memo[i][hold][transCount] = Math.max(dfs(i -1, prices, 0, transCount, memo), dfs(i-1, prices, 1, transCount-1, memo) + prices[i]);
    }
}

// TC: O(n * 2 * 3)
// SC: O(n)

Do https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/ this first then this problem.