Adapted from previous python solution, with more explanation, Time and Space O(n)


  • 0
    A
    """
    DP time:O(n), space O(n)
    
    Idea:  two dp arrays
    buy[i]:  until i, the profit I have, and the last operation I did is buying
    sell[i]: until i, the profit I have, and the last operation I did is selling
    """
    
    class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if len(prices) <= 1:
            return 0
        buy = [0] * len(prices)
        sell = [0] * len(prices)
        buy[0] = -prices[0]
        buy[1] = max(-prices[0],-prices[1])
        sell[0] = 0
        sell[1] = max(buy[0] + prices[1],sell[0])
        
        for i in range(2,len(prices)):
            buy[i] = max(buy[i-1], sell[i-2] - prices[i])
            sell[i] = max(sell[i-1],buy[i-1] + prices[i])
        return sell[-1]

Log in to reply
 

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