Question: https://oj.leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/

Question Name: Best Time to Buy and Sell Stock III

This problem is a simplified version of the challenge from Codility.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | class Solution: # @param prices, a list of integer # @return an integer def maxProfit(self, prices): if len(prices) <= 1: return 0 # maxProfitEndingHere records the maximum profit, until here (inclusive) # with zero or one transaction. maxProfitEndingHere = [0] * len(prices) lowestEndingHere = prices[0] for index in xrange(1, len(prices)): lowestEndingHere = min(lowestEndingHere, prices[index]) maxProfitEndingHere[index] = max(maxProfitEndingHere[index-1], prices[index] - lowestEndingHere) # maxProfitEndingHere records the maximum profit, after here (inclusive) # with zero or one transaction. maxProfitFromHere = [0] * len(prices) highestFromHere = prices[-1] for index in xrange(len(prices)-2, -1, -1): highestFromHere = max(highestFromHere, prices[index]) maxProfitFromHere[index] = max(maxProfitFromHere[index+1], highestFromHere - prices[index]) # Find the maximum profit, with zeor or one or two transactions. maxProfit = maxProfitEndingHere[-1] for index in xrange(len(prices)-1): profit = maxProfitEndingHere[index] + maxProfitFromHere[index+1] maxProfit = max(maxProfit, profit) return maxProfit |