# Best Time to Buy and Sell Stock with Transaction Fee
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee)
Canonical: https://scaleengineer.com/dsa/problems/best-time-to-buy-and-sell-stock-with-transaction-fee
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
**Companies:** [Citadel](https://scaleengineer.com/companies/citadel)
---
## Problem
You are given an array `prices` where `prices[i]` is the price of a given stock on the `ith` day, and an integer `fee` representing a transaction fee.

Find the maximum profit you can achieve. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction.

**Note:**

* You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
* The transaction fee is only charged once for each stock purchase and sale.

**Example 1:**

**Input:** prices = [1,3,2,8,4,9], fee = 2
**Output:** 8
**Explanation:** The maximum profit can be achieved by:
- Buying at prices[0] = 1
- Selling at prices[3] = 8
- Buying at prices[4] = 4
- Selling at prices[5] = 9
The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

**Example 2:**

**Input:** prices = [1,3,7,5,10,3], fee = 3
**Output:** 6

**Constraints:**

* `1 <= prices.length <= 5 * 104`
* `1 <= prices[i] < 5 * 104`
* `0 <= fee < 5 * 104`

# Approaches
## Brute-Force Recursion
This approach directly translates the problem into a recursive solution. For each day, we explore every possible action: if we hold a stock, we can either sell it or continue holding it; if we don't hold a stock, we can either buy one or rest. This generates a decision tree where every path represents a sequence of transactions, and we aim to find the path with the maximum profit.
**Time:** O(2^N), where N is the length of the `prices` array. For each day, the function branches into two possibilities, leading to an exponential number of calls. · **Space:** O(N), where N is the number of days. This space is used by the recursion stack.
**Pros:** Simple to conceptualize and implement.; Directly models the decision-making process at each step.
**Cons:** Extremely inefficient due to re-computation of the same subproblems.; Will result in a 'Time Limit Exceeded' error on any reasonably sized input.
### Explanation
The brute-force method uses a recursive function to explore all possible sequences of buying and selling stocks. The function takes the current day's index and a boolean indicating whether a stock is currently held. From any given state, it recursively calls itself for the next day for all possible actions (buy/rest or sell/hold) and returns the maximum profit found among these choices. This exhaustive search guarantees finding the optimal solution but at a very high computational cost.

```java
class Solution {
    public int maxProfit(int[] prices, int fee) {
        return calculate(prices, fee, 0, false);
    }

    private int calculate(int[] prices, int fee, int index, boolean holding) {
        if (index == prices.length) {
            return 0;
        }

        // Option to do nothing and move to the next day
        int doNothing = calculate(prices, fee, index + 1, holding);

        int doSomething;
        if (holding) {
            // Option to sell the stock
            doSomething = prices[index] - fee + calculate(prices, fee, index + 1, false);
        } else {
            // Option to buy the stock
            doSomething = -prices[index] + calculate(prices, fee, index + 1, true);
        }

        return Math.max(doNothing, doSomething);
    }
}
```
### Algorithm
- Define a recursive function `calculate(index, holding)` that returns the maximum profit from day `index` onwards.
- The `holding` parameter indicates if we currently possess a stock.
- **Base Case:** If `index` goes beyond the array bounds, return 0 as no more profit can be made.
- **Recursive Step:**
  - If `holding` is true (we have a stock):
    - Option 1 (Sell): `profit = prices[index] - fee + calculate(index + 1, false)`.
    - Option 2 (Hold): `profit = calculate(index + 1, true)`.
    - Return the maximum of the two options.
  - If `holding` is false (we don't have a stock):
    - Option 1 (Buy): `profit = -prices[index] + calculate(index + 1, true)`.
    - Option 2 (Rest): `profit = calculate(index + 1, false)`.
    - Return the maximum of the two options.
- The initial call is `calculate(0, false)`.

## Dynamic Programming with Memoization
The brute-force approach suffers from re-calculating the same subproblems multiple times. We can optimize this by using memoization, a top-down dynamic programming technique. We store the results of each unique state (defined by the current day and whether we hold a stock) in a cache or table. When we encounter a state we've seen before, we simply retrieve the stored result instead of re-computing it.
**Time:** O(N), where N is the number of days. Each of the `N * 2` states is computed exactly once. · **Space:** O(N) for both the memoization table (`N x 2`) and the recursion stack depth.
**Pros:** Drastically improves time complexity from exponential to linear.; Guaranteed to be efficient enough for the given constraints.; Maintains the intuitive recursive structure.
**Cons:** Requires O(N) extra space for the memoization table.; May have slightly more overhead than the iterative tabulation approach due to recursive function calls.
### Explanation
We enhance the recursive solution by adding a memoization table, typically a 2D array `memo[prices.length][2]`. The state is defined by `(index, holding)`, where `holding` is 0 for not holding a stock and 1 for holding one. Before the recursive logic, we check `memo[index][holding]`. If it contains a valid, previously computed result, we return it. Otherwise, we perform the calculation, store the result in `memo[index][holding]`, and then return it. This ensures that each of the `N * 2` states is computed only once.

```java
class Solution {
    Integer[][] memo;
    int[] prices;
    int fee;

    public int maxProfit(int[] prices, int fee) {
        this.prices = prices;
        this.fee = fee;
        this.memo = new Integer[prices.length][2];
        return calculate(0, 0); // 0: not holding, 1: holding
    }

    private int calculate(int index, int holding) {
        if (index == prices.length) {
            return 0;
        }
        if (memo[index][holding] != null) {
            return memo[index][holding];
        }

        // Case 1: Do nothing today (rest or hold)
        int doNothing = calculate(index + 1, holding);

        int doSomething;
        if (holding == 1) { // Currently holding a stock
            // Option 2: Sell the stock
            doSomething = prices[index] - fee + calculate(index + 1, 0);
        } else { // Currently not holding a stock
            // Option 2: Buy the stock
            doSomething = -prices[index] + calculate(index + 1, 1);
        }

        memo[index][holding] = Math.max(doNothing, doSomething);
        return memo[index][holding];
    }
}
```
### Algorithm
- Use the same recursive structure as the brute-force approach.
- Create a 2D memoization table, `memo[n][2]`, where `n` is the number of days. `memo[i][0]` will store the max profit from day `i` if not holding a stock, and `memo[i][1]` if holding one.
- Initialize the table with a sentinel value (e.g., `null` or -1) to indicate that a state has not been computed.
- In the recursive function, before any computation, check if the result for the current state `(index, holding)` is already in the memoization table. If so, return it directly.
- If not, compute the result as in the brute-force approach, store it in the table, and then return it.

## Dynamic Programming with Tabulation
This approach, also known as bottom-up dynamic programming, solves the problem iteratively. We build a table to store the maximum profit at each day for two possible states: holding a stock or not holding a stock. We fill the table starting from day 0 and use the results of the previous day to compute the results for the current day.
**Time:** O(N), as we iterate through the prices array once to fill the DP table. · **Space:** O(N) to store the `dp` table of size `N x 2`.
**Pros:** Efficient O(N) time complexity.; Avoids recursion overhead, which can make it slightly faster in practice than memoization.; The state transitions are very clear and easy to follow.
**Cons:** Uses O(N) space, which is not optimal for this problem.
### Explanation
We define our DP states as follows:
- `dp[i][0]`: The maximum profit achievable at the end of day `i`, given that we do not hold any stock.
- `dp[i][1]`: The maximum profit achievable at the end of day `i`, given that we hold one share of the stock.

We can establish the following recurrence relations:
- To have no stock on day `i`, we could have either rested from day `i-1` (if we had no stock) or sold the stock we held on day `i-1`. Thus, `dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i] - fee)`.
- To have a stock on day `i`, we could have either held onto the stock from day `i-1` or bought a stock today (if we had no stock on day `i-1`). Thus, `dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])`.

The base cases for day 0 are `dp[0][0] = 0` and `dp[0][1] = -prices[0]`. We iterate up to the last day and return `dp[n-1][0]`.

```java
class Solution {
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        if (n == 0) {
            return 0;
        }
        
        int[][] dp = new int[n][2];
        
        // Base case for day 0
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        
        for (int i = 1; i < n; i++) {
            // Max profit with no stock today
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i] - fee);
            
            // Max profit with a stock today
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);
        }
        
        return dp[n - 1][0];
    }
}
```
### Algorithm
- Create a 2D DP table `dp[n][2]`, where `dp[i][0]` is the max profit on day `i` ending with no stock, and `dp[i][1]` is the max profit on day `i` ending with a stock.
- **Base Case (Day 0):**
  - `dp[0][0] = 0` (start with no stock, no profit).
  - `dp[0][1] = -prices[0]` (buy on day 0).
- **Iteration:** Loop from `i = 1` to `n-1`.
  - `dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i] - fee)`.
  - `dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])`.
- **Result:** The final answer is `dp[n-1][0]`, as it's always optimal to not be holding a stock on the last day.

## Space-Optimized Dynamic Programming
This is the most optimized approach. By observing the recurrence relations in the tabular DP approach, we can see that the calculation for day `i` only depends on the values from day `i-1`. This means we don't need to store the entire DP table. We only need to keep track of the maximum profit for the two states (holding a stock and not holding one) from the previous day. This reduces the space complexity to a constant.
**Time:** O(N), as it involves a single pass through the input array. · **Space:** O(1), as we only use a few constant-space variables to store the state.
**Pros:** Optimal time complexity of O(N).; Optimal space complexity of O(1).; Very efficient and concise implementation.
**Cons:** The logic can be slightly less intuitive to grasp initially compared to the version with an explicit DP table.
### Explanation
We can optimize the space complexity of the tabular DP approach from O(N) to O(1). We only need two variables to track the maximum profit at the end of the previous day: `cash` for the state of not holding a stock, and `hold` for the state of holding a stock.

We iterate through the prices, and for each day, we calculate the new `cash` and `hold` values. The new `cash` value is the maximum of either not doing anything (keeping the old `cash` value) or selling the stock (which depends on the old `hold` value). The new `hold` value is the maximum of either holding onto the stock (keeping the old `hold` value) or buying a stock (which depends on the old `cash` value). It's important to use the `cash` value from the *previous* day when calculating the new `hold` value, so we use a temporary variable.

```java
class Solution {
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        if (n == 0) {
            return 0;
        }
        
        // `cash`: max profit if we end the day with no stock
        int cash = 0; 
        // `hold`: max profit if we end the day holding a stock
        int hold = -prices[0];
        
        for (int i = 1; i < n; i++) {
            int prev_cash = cash;
            
            // New cash state is max of (rest from prev cash) or (sell from prev hold)
            cash = Math.max(cash, hold + prices[i] - fee);
            
            // New hold state is max of (rest from prev hold) or (buy from prev cash)
            hold = Math.max(hold, prev_cash - prices[i]);
        }
        
        return cash;
    }
}
```
### Algorithm
- Initialize two variables: `cash = 0` (max profit ending with no stock) and `hold = -prices[0]` (max profit ending with a stock).
- Iterate through the prices from the second day (`i = 1` to `n-1`).
- In each iteration, update the `cash` and `hold` variables based on the previous day's values:
  - Store the previous `cash` value in a temporary variable: `prev_cash = cash`.
  - Update `cash`: `cash = max(cash, hold + prices[i] - fee)`.
  - Update `hold`: `hold = max(hold, prev_cash - prices[i])`.
- After the loop, return `cash`.

# Solutions
### Java

```java
class Solution {
public
  int maxProfit(int[] prices, int fee) {
    int f0 = 0, f1 = -prices[0];
    for (int i = 1; i < prices.length; ++i) {
      int g0 = Math.max(f0, f1 + prices[i] - fee);
      f1 = Math.max(f1, f0 - prices[i]);
      f0 = g0;
    }
    return f0;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxProfit(vector<int> &prices, int fee) {
    int n = prices.size();
    int f[n][2];
    memset(f, 0, sizeof(f));
    f[0][1] = -prices[0];
    for (int i = 1; i < n; ++i) {
      f[i][0] = max(f[i - 1][0], f[i - 1][1] + prices[i] - fee);
      f[i][1] = max(f[i - 1][1], f[i - 1][0] - prices[i]);
    }
    return f[n - 1][0];
  }
};

```

### Python

```python
class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int: f1, f2 = - prices[0], 0 for price in prices[1:]: f1 = max(f1, f2 - price) f2 = max(f2, f1 + price - fee) return f2  # class Solution : def maxProfit ( self , prices : List [ int ], fee : int ) -> int : f0 , f1 = 0 , - prices [ 0 ] for x in prices [ 1 :]: f0 , f1 = max ( f0 , f1 + x - fee ), max ( f1 , f0 - x ) return f0 ############ class Solution : def maxProfit ( self , prices , fee ): """ :type prices: List[int] :type fee: int :rtype: int """ cash = 0 hold = - prices [ 0 ] for i in range ( 1 , len ( prices )): cash = max ( cash , hold + prices [ i ] - fee ) hold = max ( hold , cash - prices [ i ]) return cash

```