Description
Given an array prices and a transaction fee, find the maximum profit. You may complete as many transactions as you like, but must pay the transaction fee for each transaction.
Examples
Input:
prices = [1,3,2,8,4,9], fee = 2Output:
8Explanation:
Buy at 1, sell at 8, buy at 4, sell at 9. Profit = (8-1-2) + (9-4-2) = 8.
Input:
prices = [7,6,4,3,1], fee = 1Output:
0Explanation:
Prices are continuously decreasing, so no profitable transactions can be made. Any buy-sell pair would result in a loss due to the transaction fee.
Input:
prices = [2,4,1,7,3,8], fee = 3Output:
5Explanation:
Buy at 1, sell at 7, then buy at 3, sell at 8. Profit = (7-1-3) + (8-3-3) = 3 + 2 = 5. Although one could buy at 2 and sell at 4, the profit (4-2-3 = -1) would be negative due to the high transaction fee.
Constraints
- •
1 ≤ prices.length ≤ 5 × 10⁴ - •
0 ≤ prices[i], fee ≤ 5 × 10⁴