Maximum Profit with Transaction Fee

Problem Description

You are given an array prices where prices[i] is the price of a given stock on the i<sup>th</sup> 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.

Naive Approach (Brute Force)

A brute-force approach would involve exploring all possible combinations of buying and selling stocks, considering the transaction fee for each transaction. This can be implemented using recursion.

Code (Python):

def max_profit_recursive(prices, fee, index, holding):
    if index == len(prices):
        return 0

    # Option 1: Do nothing
    profit = max_profit_recursive(prices, fee, index + 1, holding)

    # Option 2: Buy if not holding, sell if holding
    if not holding:
        profit = max(profit, -prices[index] + max_profit_recursive(prices, fee, index + 1, True))
    else:
        profit = max(profit, prices[index] - fee + max_profit_recursive(prices, fee, index + 1, False))

    return profit

# Initial call
# max_profit_recursive(prices, fee, 0, False)

Time Complexity: O(2ⁿ), where n is the number of days (length of the prices array), because each day we explore two options.

Space Complexity: O(n) due to the recursion depth.

Optimal Approach (Dynamic Programming)

A more efficient approach is to use dynamic programming. We can maintain two states:

• cash: Represents the maximum profit we can have if we do not hold a stock at the end of day i.
• hold: Represents the maximum profit we can have if we hold a stock at the end of day i.

Algorithm:

1. Initialize cash = 0 and hold = -prices[0] (we buy the stock on the first day).
2. Iterate through the prices array from the second day.
3. For each day:
   • Update cash as max(cash, hold + prices[i] - fee) (sell the stock today or do nothing).
   • Update hold as max(hold, cash - prices[i]) (buy the stock today or do nothing).
4. Return cash.

Code (Python):

def max_profit(prices, fee):
    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

Time Complexity: O(n), where n is the number of days (length of the prices array), as we iterate through the prices array once.

Space Complexity: O(1), as we only use two variables cash and hold.

Edge Cases

• If the prices array is empty, the maximum profit is 0.
• If the fee is very large such that no transaction is profitable, the maximum profit is 0.
• If the prices array is very small (e.g., length 1), the maximum profit is 0.

These edge cases are implicitly handled by the dynamic programming solution.