286. Best Time to Buy and Sell Stock with Transaction Fee

MediumDynamic Programming

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.

Examples

Input: [1,3,2,8,4,9] 2

Output: 8

Explanation: Buy at 1, sell at 8 (profit 8-1-2=5); buy at 4, sell at 9 (profit 9-4-2=3). Total 8.

Constraints

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

Run checks all cases above. Submit evaluates all test cases.