Share my solution in python


  • 0
    Y

    this solution is almost the fastest one in python by far. It's very simple and clear. It takes O(n) O(n). Feel free to leave any comments.

    class Solution:
        def reverseAndNeg(self, l):
            l.reverse()
            for i in range(0, len(l)):
                l[i] *= -1
        def dp(self, l):
            max = 0
            min = 0
            ret = []
            for i in range(0, len(l)):
                ret.append(l[max] - l[min])
                if l[i] > l[max]:
                    ret[i] = l[i] - l[min]
                    max = i
                elif l[i] < l[min]:
                    max = i
                    min = i
            return ret
        # @param prices, a list of integer
        # @return an integer
        def maxProfit(self, prices):
            ret = 0
            frontward = self.dp(prices)
            self.reverseAndNeg(prices)
            backward = self.dp(prices)
            for i in range(0, len(prices)):
                if (frontward[i] + backward[len(prices) - 1 - i] > ret):
                    ret = frontward[i] + backward[len(prices) - 1 - i]
            return ret

Log in to reply
 

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