[leetcode]Best Time to Buy and Sell Stock III @ Python
題意：
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
