c# - Best Time to Buy and Sell Stock at most two transactions

Question

Question: Best Time to Buy and Sell Stock at most two transactions.

Say you have an array for which the i-th 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: 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 

There are multiple solutions by optimizing step-by-step and trying to understand them, but don't clearly understand some optimizations, please see below questions denoted by Q:

Solution b: Understood this solution If we slight swap the two 'for' loops:

// Solution b
public int MaxProfitDpCompact1T(int[] prices) {
    if (prices.Length == 0) return 0;
    
    var dp = new int[3, prices.Length];   

    var min = new int[3];
    Array.Fill(min, prices[0]);

    for (int i = 1; i < prices.Length; i++) {
    
        for (int k = 1; k <= 2; k++) {
            min[k] = Math.Min(min[k], prices[i] - dp[k-1, i-1]);
            dp[k, i] = Math.Max(dp[k, i-1], prices[i] - min[k]);
        }
    }

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

Solution c: We need to save min for each transaction, so there are k 'min'.

We can find the second dimension (variable i) is only dependent on the previous one (i-1), so we can compact this dimension.

==> Q: we have many i depends on i-1 for many Dynamic Programming, in which case this can be compacted and which case can't? I'm so confused

(We can choose the first dimension (variable k) as well since it is also only dependent on its previous one k-1, but can't compact both.)

==> Q: the below code is compacted on i, if we compact on k, then how the code looks like? Have no idea.

// Solution c
public int MaxProfitDpCompact2(int[] prices) {
    if (prices.Length == 0) return 0;

    var dp = new int[3];

    var min = new int[3];
    Array.Fill(min, prices[0]);

    for (int i = 1; i < prices.Length; i++)  {
        for (int k = 1; k <= 2; k++) {
            min[k] = Math.Min(min[k], prices[i] - dp[k-1]);
            dp[k] = Math.Max(dp[k], prices[i] - min[k]);
        }
    }

    return dp[2];
}

question from:https://stackoverflow.com/questions/65602471/best-time-to-buy-and-sell-stock-at-most-two-transactions

Answer 1

Waitting for answers