Short python solution, O(n) runtime, O(1) space


  • 6
    J

    The question is simple. You want to find the difference of the maximum and the minimum. The only trick is that the bigger number should come after the smaller number.

    So, here is how I tackled it. Instead of going forward, I scanned through the list of prices backward to store the current maximum number. Update the biggest difference along the way.

    class Solution:
        # @param prices, a list of integer
        # @return an integer
        def maxProfit(self, prices):
            length = len(prices)
            if length==0:
                return 0
            temp = prices[length-1]
            res = 0
            for i in range(length-1,-1,-1):
                temp = max(temp,prices[i])
                if temp - prices[i] > res:
                    res = temp - prices[i]
            return res

  • 7
    D
    class Solution:
        # @param prices, a list of integer
        # @return an integer
        def maxProfit(self, prices):
            if len(prices) == 0:
                return 0
            minPrice = prices[0]
            maxProfit = 0
            for i in range(0, len(prices)):
                if prices[i] < minPrice:
                    minPrice = prices[i]
                if prices[i] - minPrice > maxProfit:
                    maxProfit = prices[i] - minPrice
            return maxProfit

  • -1
    S
    def maxProfit(self, prices):
            if len(prices) < 1:
                return prices
            if len(prices) > 1:
                profit = []
                for i in range(1,len(prices)):
                    for j in range(0,i):
                        profit.append(prices[i]-prices[j])
                return max(profit)
    

    I did in a pretty similar way, but i got an error saying memory limit exceeded. why is that?


  • 0
    E

    Very nice idea!Thank you for sharing.


  • 0
    E

    Actually, not similar.you got o(n^2) runtime,and he got o(n).The list you created is too large.


Log in to reply
 

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