Best Time to Buy and Sell Stock V

• Define a recursive function solve(i, k) that computes the maximum profit from day i to n-1 with at most k transactions.
• The base cases for the recursion are:
  • If k is 0, no more transactions can be made, so the profit is 0.
  • If i is greater than or equal to n-1, there are not enough days to make a transaction, so the profit is 0.
• In the recursive step for solve(i, k), we consider two main possibilities:
  1. Skip day i: We don't start a transaction on day i. The maximum profit is then found by solving the subproblem for the remaining days, which is solve(i + 1, k).
  2. Start a transaction on day i: We can pair day i with any subsequent day j (where j > i) to form a transaction. The profit for this single transaction is |prices[j] - prices[i]|. After this transaction, which ends on day j, we can start the next transaction from day j+1. The profit from the remaining k-1 transactions is solve(j + 1, k - 1). We iterate through all possible j from i+1 to n-1 and take the one that maximizes the total profit.
• The result for solve(i, k) is the maximum of the outcomes from these two possibilities.
• To avoid recomputing the same subproblems, we use a 2D array memo[i][k] for memoization.

We can define a DP state dp[i][k] as the maximum profit achievable using the subarray of prices from day i to the end, with at most k transactions allowed.

The goal is to compute dp[0][k].

The recurrence relation can be formulated as follows: dp[i][k] = max(option1, option2)

• Option 1: Don't transact starting at day i We skip day i and the problem reduces to finding the max profit from day i+1 onwards with k transactions. The profit is dp[i+1][k].

• Option 2: Start a transaction at day i We start a transaction at day i and end it at some future day j > i. The profit from this transaction is |prices[j] - prices[i]|. After this transaction concludes on day j, we are left with k-1 transactions and can continue from day j+1. We must try every possible j from i+1 to n-1 and choose the one that yields the maximum total profit. This is expressed as: max_{j=i+1}^{n-1} (|prices[j] - prices[i]| + dp[j+1][k-1])

Combining these, the full recurrence is: dp[i][k] = max(dp[i+1][k], max_{j=i+1}^{n-1} (|prices[j] - prices[i]| + dp[j+1][k-1]))

This can be implemented using a recursive function with a 2D memoization table to store the results of dp[i][k] and avoid redundant calculations.

1import java.util.Arrays;2 3class Solution {4    private long[][] memo;5    private int[] prices;6    private int n;7 8    public long maxProfit(int[] prices, int k) {9        this.prices = prices;10        this.n = prices.length;11        this.memo = new long[n][k + 1];12        for (long[] row : memo) {13            Arrays.fill(row, -1);14        }15        return solve(0, k);16    }17 18    private long solve(int i, int k) {19        if (k == 0 || i >= n - 1) {20            return 0;21        }22        if (memo[i][k] != -1) {23            return memo[i][k];24        }25 26        // Option 1: Skip day i27        long res = solve(i + 1, k);28 29        // Option 2: Start a transaction on day i30        for (int j = i + 1; j < n; j++) {31            long currentProfit = Math.abs((long)prices[j] - prices[i]);32            long futureProfit = (j + 1 < n) ? solve(j + 1, k - 1) : 0;33            res = Math.max(res, currentProfit + futureProfit);34        }35 36        return memo[i][k] = res;37    }38}

• Create a 2D DP table dp[k+1][n] of type long, where dp[j][i] stores the maximum profit using at most j transactions up to day i.
• Initialize the dp table with zeros. The 0th row and 0th column will remain 0, representing 0 transactions or 0 days.
• Iterate through the number of transactions j from 1 to k.
• For each j, iterate through the days i from 1 to n-1.
• Inside the inner loop, maintain two variables, maxDiff and maxSum, to track the optimal values needed for the transition.
• Update maxDiff and maxSum based on the results from the previous transaction count (j-1) and the price on the previous day (i-1).
  • maxDiff = max(maxDiff, dp[j-1][p-1] - prices[p])
  • maxSum = max(maxSum, dp[j-1][p-1] + prices[p])
  • These are updated incrementally for p = i-1.
• Calculate the profit if the j-th transaction ends on day i. This is max(prices[i] + maxDiff, -prices[i] + maxSum).
• The value of dp[j][i] is the maximum of either not ending a transaction at day i (dp[j][i-1]) or ending one (profit_with_new_txn).
• After filling the table, the final answer is dp[k][n-1].

We can significantly improve the time complexity by changing our DP state and optimizing the transition. Let dp[j][i] be the maximum profit using at most j transactions within the first i+1 days (i.e., prices[0...i]).

The recurrence relation is: dp[j][i] = max(dp[j][i-1], profit_if_last_txn_ends_at_i)

Here, dp[j][i-1] represents the case where we don't end a transaction on day i. The second term represents the case where the j-th transaction ends on day i. It must have started on some day p < i. The profit is the sum of the profit from j-1 transactions up to day p-1 (dp[j-1][p-1]) and the profit of the new transaction |prices[i] - prices[p]|. We need to maximize this over all p < i:

profit_if_last_txn_ends_at_i = max_{0 <= p < i} (dp[j-1][p-1] + |prices[i] - prices[p]|)

This inner max operation would still lead to an O(n) transition. We can optimize it by expanding the absolute value: |prices[i] - prices[p]| = max(prices[i] - prices[p], prices[p] - prices[i])

So we need to find:

1max( max_{p<i}(dp[j-1][p-1] - prices[p]) + prices[i],  max_{p<i}(dp[j-1][p-1] + prices[p]) - prices[i] )

Let maxDiff = max_{p<i}(dp[j-1][p-1] - prices[p]) and maxSum = max_{p<i}(dp[j-1][p-1] + prices[p]). As we iterate i from 1 to n-1, we can update maxDiff and maxSum in O(1) time by considering the value for p = i-1. This removes the inner loop and makes the overall algorithm O(k*n).

1class Solution {2    public long maxProfit(int[] prices, int k) {3        int n = prices.length;4        if (n < 2) {5            return 0;6        }7 8        long[][] dp = new long[k + 1][n];9 10        for (int j = 1; j <= k; j++) {11            long maxDiff = Long.MIN_VALUE;12            long maxSum = Long.MIN_VALUE;13            for (int i = 1; i < n; i++) {14                // Update maxDiff and maxSum using p = i-115                // Profit from j-1 transactions must end before day i-1, so we look at dp[j-1][i-2]16                long prevDpVal = (i > 1) ? dp[j - 1][i - 2] : 0;17                maxDiff = Math.max(maxDiff, prevDpVal - prices[i - 1]);18                maxSum = Math.max(maxSum, prevDpVal + prices[i - 1]);19 20                // Profit if the j-th transaction ends on day i21                long profitWithNewTxn = Math.max(prices[i] + maxDiff, -prices[i] + maxSum);22 23                // dp[j][i] is the max of not ending a txn at i vs. ending one at i24                dp[j][i] = Math.max(dp[j][i - 1], profitWithNewTxn);25            }26        }27 28        return dp[k][n - 1];29    }30}

Space Optimization: Notice that calculating dp[j] only requires values from dp[j-1]. We can optimize the space to O(n) by using only two arrays, one for the previous state (j-1) and one for the current state (j).