Best Time to Buy and Sell Stock V

This approach uses recursion with memoization, which is a form of top-down dynamic programming. We define a function that calculates the maximum profit from a given day with a certain number of transactions remaining. The state is defined by (current_day, transactions_left). For each state, we explore all possible future transactions, leading to a high time complexity.

• 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.

import java.util.Arrays;

class Solution {
    private long[][] memo;
    private int[] prices;
    private int n;

    public long maxProfit(int[] prices, int k) {
        this.prices = prices;
        this.n = prices.length;
        this.memo = new long[n][k + 1];
        for (long[] row : memo) {
            Arrays.fill(row, -1);
        }
        return solve(0, k);
    }

    private long solve(int i, int k) {
        if (k == 0 || i >= n - 1) {
            return 0;
        }
        if (memo[i][k] != -1) {
            return memo[i][k];
        }

        // Option 1: Skip day i
        long res = solve(i + 1, k);

        // Option 2: Start a transaction on day i
        for (int j = i + 1; j < n; j++) {
            long currentProfit = Math.abs((long)prices[j] - prices[i]);
            long futureProfit = (j + 1 < n) ? solve(j + 1, k - 1) : 0;
            res = Math.max(res, currentProfit + futureProfit);
        }

        return memo[i][k] = res;
    }
}