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

This series of Buy and Sell Stock I~VI on Leetcode is a great practice for Dynamic Programming – State Machine. Therefore I prepared blogs for each of them and hopefully it would help you to understand them better. You can find the relations of them at the bottom and feel free to leave any comments. 

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.

Dynamic programming 1 – State machine

State transitions.

Similar to [Leetcode]122. Best Time to Buy and Sell Stock II, this is also a two-state problem, except that there’s a fee for each transaction. Therefore we can define dp[i] as the largest profit we can make on day i and we have transition functions:

cash[i] = max(cash[i-1],hold[i-1]+prices[i]-fee)
hold[i] = max(hold[i-1],cash[i-1]-prices[i])

In this case we could have a O(n) time complexity and O(n) space complexity solution. Moreover, we can reduce the space complexity to O(1) since both cash[i] and hold[i] only depend on cash[i-1] and hold[i-1].

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        cash,hold = 0, -prices[0]
        for i in range(1,len(prices)):
            pre_cash = cash
            cash = max(cash,hold+prices[i]-fee)
            hold = max(hold,pre_cash-prices[i])
        return cash

Dynamic programming 2

Similar to [Leetcode]188. Best Time to Buy and Sell Stock IV, we can have another transition function as:

dp[i] = max(dp[i-1],
        prices[i]-prices[j]+dp[j-1]-fee)

Therefore with a nested-loop, we have this O(n^2) solution:

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        dp = [max(0,prices[i]-prices[0]-fee) for i in range(len(prices))]
        for i in range(1,len(prices)):
            for j in range(1,i):
                dp[i] = max(dp[i],dp[j-1]+prices[i]-prices[j]-fee)
            dp[i] = max(dp[i],dp[i-1])
        return dp[-1]

With a small tweak of the transition function, instead of looking for max(prices[i]-prices[j]+dp[j-1]-fee), we would look for min(prices[j]-dp[j-1]), reducing the time complexity to O(1).

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        if len(prices) < 2:
            return 0
        dp = [0] * (len(prices))
        low = prices[0]
        for i in range(1,len(prices)):
            low = min(low,prices[i]-dp[i-1])
            dp[i] = max(dp[i-1],prices[i]-low-fee)
        return dp[-1]

Greedy

The general idea is to buy it at the lowest price and sell it at the highest. However, since there’s a fee for each transaction, it would affect our decisions. Take prices=[1,4,3,9],fee=2 as an example, if we buy 1 and sell 3, then we wouldn’t achieve the largest profit as (4-1)-fee+(9-3)-fee<(9-1)-fee.

One approach is that, after we buy 1 and sell 4 as 4-1-fee>0, we can assign 4-fee as our lowest price. When we find 9>(4-fee)+fee, then we can add 9-(4-fee)-fee to our profit. By using price[i]-fee, we still hold the chance to explore the potential larger profit.

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        ret,buy = 0,float('inf')
        for p in prices:
            if p < buy:
                buy = p
            elif p>buy+fee:
                ret += p-buy-fee
                buy = p - fee
        return ret
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments