Python solution


  • 0
    N
        def maxProfit(self, prices, fee):
            """
            :type prices: List[int]
            :type fee: int
            :rtype: int
            """
            
            # two states:
            # max profit when the last action was a buy (does not need to be exactly on that date)
            # max profit when the last action was a sell 
            
            s0 = -prices[0]
            s1 = 0
            
            for price in prices:
                # could hold given s0, or buy given s1
                f0 = max(s0, s1 - price)
                # hold or sell given s0
                f1 = max(s1, s0 + price - fee)
                
                s0, s1 = f0, f1
                
            return s1
    

  • 0
    S

    @nicksun said in Python solution:

    s1 - price

    Hi Nicksun,
    Could you explain to me the key points to solve this problem?
    I don't understand your code though it seems so simple and neat.
    What is s0 and s1?
    Can you elaborate on how you code this problem
    Thank you
    S


  • 0
    N

    @Song_on_the_road Yeah so this is a dp problem. You want to track two states, last action was buy/sell. Note if you have buy, noAction, noAction then it is treated as last action was buy. s0 and s1 are the initial states: if you buy, your net profit is -prices[0] and since you cannot sell initially, s1=0. The lines in the for loop are basically how you update your profit. Whenever you buy, you subtract off the current price and similarly for the sell.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.