Leetcode 714. Best Time to Buy and Sell Stock with Transaction Fee (Python)

Related Topic

Dynamic-Programming.

Description

Your are given an array of integers prices, for which the i-th element is the price of a given stock on day i; and a non-negative integer fee representing a transaction fee.

You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. You may not buy more than 1 share of a stock at a time (ie. you must sell the stock share before you buy again.)

Return the maximum profit you can make.

Sample I/O

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.

Note:

• 0 < prices.length <= 50000.
• 0 < prices[i] < 50000.
• 0 <= fee < 50000.

Methodology

This question solved by Dynamic Programming.It is similar with question 309. Unique Paths. The difference, this question has no cool down but with transcation fee for each transcation.

Based on the question, each element should have two status which are buy and sell. You can actually convert these two status to Hold stock or unhold stock:

• Hold stock: At the end of today, the maxmium profit if you hold stock and these can be two conditions:
  1. You bought the stock today
  2. You did not sell the stock that you bought before
• Unhold stock: At the end of today, the maxmium profit if you unhold stock and these can be two conditions as well:
  1. You sold the stock today plus transcation fee
  2. You did not buy any stock after you sold last stock

The answer should be when you not hold stock, the maxmium profit.

Find the base case:

Create two dp list one is called hold, the other called unhold. each element represent the maxmium profit at the end of ith day. Init the first element of hold to -price[0] Init the first element of unhold to 0

Find the pattern:

There should be two patterns one for hold stock and the other one for unhold stock:

• hold stock: max(you bought the stock today, you bought the stock before but not sold it yet)
• unhold stock: max(you sold the stock today + transcation fee, you did not buy any stock after sold last stock)

Answer:

last element of unhold stock.

Code

def maxProfit(self, prices: List[int], fee: int) -> int:
        size = len(prices)
        hold = [0]*size
        unhold = [0]*size
        hold[0] = -prices[0]
        for i in range(1,size):
            hold[i] = max(unhold[i-1]-prices[i], hold[i-1])
            unhold[i] = max(hold[i-1]+prices[i]-fee, unhold[i-1])
        return unhold[-1]

BigO

Then iterate both dp lists, it will cost O(2L). generally it is O(L)