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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def max_profit(prices, fee)
   n = prices.size
   profit = 0

   for i in (0..n-2)
      if (prices[i] < prices[i+1] - fee)
         profit += price[i+1] - prices[i] - fee
      end
   end
   return profit
end

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

# @param {Integer[]} prices
# @param {Integer} fee
# @return {Integer}
def max_profit(prices, fee)
   cash = 0
   hold = -prices[0]
   
   for i in (1..prices.size-1)
      cash = [cash, hold + prices[i] - fee].max
      hold = [hold, cash - prices[i]].max
   end
   return cash
end