Best Time to Buy and Sell Stock with Transaction Fee

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.

Example 2:

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

Constraints:

• 1 <= prices.length <= 5 * 10^4
• 1 <= prices[i] <= 5 * 10^4
• 0 <= fee < 5 * 10^4

Maximum Profit with Transaction Fee

This problem asks us to find the maximum profit that can be achieved by buying and selling a stock any number of times, given a transaction fee for each transaction. We are given an array prices representing the price of the stock on each day and an integer fee representing the transaction fee. We need to find the maximum profit we can achieve by buying and selling the stock, paying the transaction fee for each completed transaction (buy and sell). We cannot engage in multiple transactions simultaneously, meaning we must sell the stock before we buy again.

Naive Approach (Brute Force)

A brute-force approach would involve trying every possible combination of buy and sell transactions and calculating the profit for each combination. This approach would have exponential time complexity and is not practical for larger input sizes.

Optimal Approach (Dynamic Programming)

We can use dynamic programming to solve this problem efficiently. We maintain two variables:

• cash: Represents the maximum profit we can have if we don't hold any stock at the end of the day.
• hold: Represents the maximum profit we can have if we hold a stock at the end of the day.

We iterate through the prices array, updating these two variables at each day.

1. On each day, the cash can be updated by either remaining the same (not selling any stock) or selling the stock we are holding. If we sell the stock, the profit becomes hold + price - fee.
2. On each day, the hold can be updated by either remaining the same (not buying any stock) or buying the stock today. If we buy the stock today, the profit becomes cash - price.

Here is the code:

def maxProfit(prices, fee):
    cash = 0  # Maximum profit if we don't hold any stock
    hold = -prices[0]  # Maximum profit if we hold a stock

    for i in range(1, len(prices)):
        cash = max(cash, hold + prices[i] - fee)
        hold = max(hold, cash - prices[i])

    return cash

# Example usage:
prices = [1, 3, 2, 8, 4, 9]
fee = 2
profit = maxProfit(prices, fee)
print(f"Maximum profit: {profit}")  # Output: 8

prices = [1,3,7,5,10,3]
fee = 3
profit = maxProfit(prices, fee)
print(f"Maximum profit: {profit}")

Big(O) Time Complexity Analysis

The algorithm iterates through the prices array once. Inside the loop, only constant time operations are performed (max function and variable assignments). Therefore, the time complexity is O(n), where n is the length of the prices array.

Big(O) Space Complexity Analysis

The algorithm uses only two variables, cash and hold, to store the maximum profits. The space used does not depend on the input size. Therefore, the space complexity is O(1), which is constant space.

Edge Cases

• Empty prices array: If the prices array is empty, the profit is 0. The given code handles this case correctly because the loop will not execute.
• Single element prices array: If the prices array has only one element, no transaction can be made, and the profit is 0. The given code initializes hold to -prices[0] and the loop does not execute. So cash remains 0.
• Fee is zero: If the fee is zero, then this problem is just the Best Time to Buy and Sell Stock with Multiple Transactions.
• Fee is very large: If the fee is larger than the difference between the highest and lowest prices, then no transaction makes sense, and the profit is 0.

In summary, the dynamic programming approach provides an efficient and straightforward solution for maximizing profit with a transaction fee.