Best Time to Buy and Sell Stock with Transaction Fee

Problem Description

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

Key Insights

• To maximize profit, we must decide when to buy and sell stocks while considering the transaction fee.
• Tracking two states: holding a stock and not holding a stock, helps in determining the maximum profit.
• Dynamic programming approach can be utilized to maintain profits based on previous decisions.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

We can use a dynamic programming approach with two variables to represent the maximum profit when holding a stock and when not holding a stock.

1. Initialize two variables: cash (profit when not holding stock) and hold (profit when holding stock).
2. Iterate through each price in the prices array:
   • Update the cash profit as the maximum of the previous cash or the profit from selling the stock (current price plus the previous hold).
   • Update the hold profit as the maximum of the previous hold or the profit from buying the stock (previous cash minus the current price and fee).
3. The final maximum profit will be stored in the cash variable.

Code Solutions