题意：
?
Say you have an array for which the ith element is the price of a given stock on day i.
?
Design an algorithm to find the maximum profit. You may complete at most two transactions.
?
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
?
解题思路： 交易市场的“低买高卖" 法则(buy low and sell high' )
?
只允许做两次交易，这道题就比前两道要难多了。解法很巧妙，有点动态规划的意思：
?
开辟两个数组p1和p2，p1[i]表示在price[i]之前进行一次交易所获得的最大利润，
?
p2[i]表示在price[i]之后进行一次交易所获得的最大利润。
?
则p1[i]+p2[i]的最大值就是所要求的最大值，
?
而p1[i]和p2[i]的计算就需要动态规划了，看代码不难理解。
?
?
?
复制代码
class Solution:
? ? # @param prices, a list of integer
? ? # @return an integer
? ? def maxProfit(self, prices):
? ? ? ? n = len(prices)
? ? ? ? if n <= 1: return 0
? ? ? ? p1 = [0] * n
? ? ? ? p2 = [0] * n
? ? ? ??
? ? ? ? minV = prices[0]
? ? ? ? for i in range(1,n):
? ? ? ? ? ? minV = min(minV, prices[i]) ? ? ? # Find low and buy low
? ? ? ? ? ? p1[i] = max(p1[i - 1], prices[i] - minV)
? ? ? ??
? ? ? ? maxV = prices[-1]
? ? ? ? for i in range(n-2, -1, -1):
? ? ? ? ? ? maxV = max(maxV, prices[i]) ? ? # Find high and sell high
? ? ? ? ? ? p2[i] = max(p2[i + 1], maxV - prices[i])
? ? ? ??
? ? ? ? res = 0
? ? ? ? for i in range(n):
? ? ? ? ? ? res = max(res, p1[i] + p2[i])
? ? ? ? return res