Best Time to Buy and Sell Stock with Transaction Fee

Photo by Sonja Langford on Unsplash

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

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 * 104
• 1 <= prices[i] < 5 * 104
• 0 <= fee < 5 * 104

Code first then will see the explanation ;-)

Explanation :
Here’s the explanation with an example:
prices = [1, 3, 4, 5, 4, 8], fee = 2
Do you take profit of day0 to day3 (prices[3] — prices[0] = 4) and day4 to day5(prices[5] — prices[4] = 4) ? Option 1
Or do you take profit of day0 to day5(prices[5] — prices[0] = 7)? Option 2
Because transaction fee = 2 , (7–2) > (4–2 + 4–2), 2nd option is better.
So we need to avoid greedily setting ‘minimum = day4’ , because sell at $5 and buy again at $4 only give us $1 more profit yet costs $2 more transaction fee.
Open a new transaction only if prices[today] < prices[yesterday] — fee. That’s why we set ‘minimum = prices[i] — fee’

For those who still struggle to understand, the why minimum = prices[i] - fee has nothing to do with buying; it is used for later consideration if there is a better (higher) selling price compared to the previously selling price, to cancel out the transaction fee and merge two transactions to one.

Dry run :

p = [1, 2, 4, 5, 3, 8, 6, 4, 5, 7], fee = 2

min = 1

i = 1 :- 2 is neither less than min (1) nor greater than min + fee (3) ; so skip
i = 2 :- 4 > min+fee(3) ; so profit = (4–2–1) = 1 and min = 4-fee = 2
i = 3 :- 5 > min+fee(2+2 = 4); so profit = profit + (5-fee-min) = (4 — fee — 1) + (5 — fee — (4 — fee)) = 4-fee-1+5-fee-4+fee = (5–1 — fee) = 2
Thus for p[3] = 5, the problem is effectively treated as bought at 1 and sold at 5
min = 5-fee = 3

i = 4 :- 3 is neither less than min (3) nor greater than min+fee (5) ; so skip
i = 5 :- 8 > min+fee(3); so profit = profit + (8-fee-min) = 2 + (8–2–3) = 5 and min = 8-fee = 6.
Thus for p[5] = 8, the problem is effectively treated as bought at 1 and sold at 8

i = 6 :- 4 < min (6); so min = 4 (That means we are allowed to start a fresh transaction from 4)

Transaction 2 effectively starts from here

i = 7 :- 5 is neither less than min (4) nor greater than min + fee (6) ; so skip
i = 8 :- 6 is neither less than min (4) nor greater than min + fee (6) ; so skip
i = 9 :- 7 > min + fee (6); so profit = proffit + (7-fee-min) = 5 + (7 -2–4) = 5 +1 = 6

Hence final profit = 6