Best Time to Buy and Sell Stock with Transaction Fee
shitgpt
 One transaction only
 Two transactions only
 Cooldown period (cannot buy on the same day you sell)
 You can have many transactions
 transaction fees will lower your profit
Fill out the following sections:
Define the Interface Input: prices (array of positive integers), fee (positive integer) Output: profit (integer)
Identify the Invariants
 fee
 prices
Identify the constraints
 Buy only after you sell (You cannot have any open transactions)
 You cannot buy more than 1 share of the stock
Search the Problem Space
 maximum profit
Classify the Problem
 maximize something??
 DP
Analyze the Examples
Solve the Problem by Hand
 Two options, we can buy at 1 and sell at 8, buy 4 and sell 9
Describe the Pattern
 Minimize the number of transactions to get the maximum profit.
 If you have a profit of 0 or negative, don’t consider that transaction
9  1 = 8  2
6
8  1 = 7  2 = 5
9  4 = 5  2 = 3
= 8
Brute Force Approach


If I sell on a given day. I can buy again on that day.
[1, 3, 2, 8, 4, 9] [1, 3, 2, 8, 15, 4] ==> profit
Analyze Time and Space Complexity
Time: O( ) Space: O( )
Outline the Solution

