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.
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 = [7,1,5,3,6,4], fee = 1
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5 - 1 - 1 = 3.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6 - 3 - 1 = 2.
Total profit is 3 + 2 = 5.
Example 2:
Input: prices = [1,3,7,5,10,3], fee = 3
Output: 6
Explanation: The total profit is (10 - 1) - 3 = 6.
Example 3:
Input: prices = [9,1,3,5,5,4,3,7,6,10,3,2,18], fee = 3
Output: 19
This is a classic stock-trading dynamic programming problem with a transaction fee. The key is to track two states: the best profit when holding a stock and the best profit when not holding one. On each day, you decide whether to buy, sell, or do nothing, while making sure the fee is applied correctly and only one position is held at a time. The optimal solution runs in linear time and handles all the sample cases efficiently.
