# Best Time to Buy and Sell Stock V
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-v)
Canonical: https://scaleengineer.com/dsa/problems/best-time-to-buy-and-sell-stock-v
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
---
## Problem
You are given an integer array `prices` where `prices[i]` is the price of a stock in dollars on the `ith` day, and an integer `k`.

You are allowed to make at most `k` transactions, where each transaction can be either of the following:

* **Normal transaction**: Buy on day `i`, then sell on a later day `j` where `i < j`. You profit `prices[j] - prices[i]`.
* **Short selling transaction**: Sell on day `i`, then buy back on a later day `j` where `i < j`. You profit `prices[i] - prices[j]`.

**Note** that you must complete each transaction before starting another. Additionally, you can't buy or sell on the same day you are selling or buying back as part of a previous transaction.

Return the **maximum** total profit you can earn by making **at most** `k` transactions.

**Example 1:**

**Input:** prices = \[1,7,9,8,2\], k = 2

**Output:** 14

**Explanation:**

We can make $14 of profit through 2 transactions: 
* A normal transaction: buy the stock on day 0 for $1 then sell it on day 2 for $9.
* A short selling transaction: sell the stock on day 3 for $8 then buy back on day 4 for $2.

**Example 2:**

**Input:** prices = \[12,16,19,19,8,1,19,13,9\], k = 3

**Output:** 36

**Explanation:**

We can make $36 of profit through 3 transactions: 
* A normal transaction: buy the stock on day 0 for $12 then sell it on day 2 for $19.
* A short selling transaction: sell the stock on day 3 for $19 then buy back on day 4 for $8.
* A normal transaction: buy the stock on day 5 for $1 then sell it on day 6 for $19.

**Constraints:**

* `2 <= prices.length <= 103`
* `1 <= prices[i] <= 109`
* `1 <= k <= prices.length / 2`

# Approaches
## Recursive Approach with Memoization
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.
**Time:** O(k * n^2) because for each state `(i, k)`, we iterate from `j = i+1` to `n-1`, which takes O(n) time. There are `k*n` states. · **Space:** O(k * n) for the memoization table.
**Pros:** The logic is a direct translation of the problem statement, making it relatively straightforward to understand.; It correctly models the sequential, non-overlapping nature of transactions.
**Cons:** The time complexity of O(k * n^2) is too slow for the given constraints and will likely result in a 'Time Limit Exceeded' error.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- 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.

## Optimized Dynamic Programming
This approach uses bottom-up dynamic programming with a crucial optimization. The DP state `dp[j][i]` is defined as the maximum profit using at most `j` transactions considering prices up to day `i`. The key idea is to optimize the calculation of the state transition. Instead of an inner loop to find the best start day for a transaction ending on day `i`, we maintain two helper variables that track the necessary maximums from previous calculations. This reduces the complexity of each transition to O(1).
**Time:** O(k * n) because of the two nested loops: one for transactions `j` (from 1 to `k`) and one for days `i` (from 1 to `n-1`). The inner calculations are O(1). · **Space:** O(k * n) for the DP table. This can be optimized to O(n) by only storing the DP results for the previous transaction count.
**Pros:** Highly efficient with O(k*n) time complexity, which passes the given constraints.; It is a systematic way to solve the problem by building up the solution from smaller subproblems.
**Cons:** The DP state and transition logic are more complex and less intuitive to derive compared to the straightforward recursive solution.
### Explanation
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:
`max( 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).

```java
class Solution {
    public long maxProfit(int[] prices, int k) {
        int n = prices.length;
        if (n < 2) {
            return 0;
        }

        long[][] dp = new long[k + 1][n];

        for (int j = 1; j <= k; j++) {
            long maxDiff = Long.MIN_VALUE;
            long maxSum = Long.MIN_VALUE;
            for (int i = 1; i < n; i++) {
                // Update maxDiff and maxSum using p = i-1
                // Profit from j-1 transactions must end before day i-1, so we look at dp[j-1][i-2]
                long prevDpVal = (i > 1) ? dp[j - 1][i - 2] : 0;
                maxDiff = Math.max(maxDiff, prevDpVal - prices[i - 1]);
                maxSum = Math.max(maxSum, prevDpVal + prices[i - 1]);

                // Profit if the j-th transaction ends on day i
                long profitWithNewTxn = Math.max(prices[i] + maxDiff, -prices[i] + maxSum);

                // dp[j][i] is the max of not ending a txn at i vs. ending one at i
                dp[j][i] = Math.max(dp[j][i - 1], profitWithNewTxn);
            }
        }

        return dp[k][n - 1];
    }
}
```
**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`).
### Algorithm
- 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]`.