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

Problem¶

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).
• The transaction fee is only charged once for each stock purchase and sale.

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.

Solve¶

I track the profit I can make the most of when I:

• Not holding any stock bestProfit[0]
• Holding a stock bestProfit[1]

With each step of prices change:

• If I don’t want to holding stock in this step, my bestProfit[0] is affect by two case:

  • I could try to sell my currently holding stock last_bestProfit[1] and get last_bestProfit[1] + price - fee asset value
  • or I could do not thing and keep last_bestProfit[0] asset value

• If I want to holding a stock now, my bestProfit[1] is also affect by two case:

  • I could try to buy a stock, which make my asset value down to last_bestProfit[0] - price
  • or I could doing any thing and keep last_bestProfit[1]

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        bestProfit = [0, 0]
        for step, price in enumerate(prices):
            if step == 0:
                bestProfit[1] = -price
                continue
            tmp = bestProfit[0]
            bestProfit[0] = max(bestProfit[0], bestProfit[1] + price - fee)
            bestProfit[1] = max(bestProfit[1], tmp - price)
        return bestProfit[0]