Accepted python solution


  • 1
    M

    The idea is, find all buy/sell pairs if we can buy/sell multiple times, and find the possible one time buy/sell based on that. The buy/sell points must be in the multiple time combinations

    class Solution:
        # @param prices, a list of integer
        # @return an integer
        def maxProfit(self, prices):
            multiple_buy_sell = []
            buy = None
            sell = None
            for price in prices:
                if buy is None:
                    buy = price
                else:
                    if sell is None:
                        if price <= buy:
                            buy = price
                        else:
                            sell = price
                    elif price >= sell:
                        sell = price
                    else:
                        multiple_buy_sell.append((buy, sell))
                        buy = price
                        sell = None
            if buy != None and sell != None:
                multiple_buy_sell.append((buy, sell))
            possible_profits = []
            for i in xrange(len(multiple_buy_sell)):
                buy = multiple_buy_sell[i][0]
                for j in xrange(i, len(multiple_buy_sell)):
                    sell = multiple_buy_sell[j][1]
                    possible_profits.append(sell-buy)
            if not possible_profits:
                return 0
            else:
                return max(possible_profits)

Log in to reply
 

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