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).
思路2：兩次遍歷显拜。
- 第一次從左到右诗祸，得到從開始到第 i 天盲憎，所能獲得的最大收益况毅。
- 第二次從右到左晓殊，得到從第 i 天到最后一天碗短，所能獲得的最大收益。
最后悦陋，對(duì)于任意的 i (0 <= i < size)蜈彼，它把數(shù)組分成兩部分，這兩部分的最大收益之和就是最終的收益俺驶。找出其中最大的那個(gè)柳刮。
可以把數(shù)組一切為2，[0, i] 為第一次交易痒钝， [i, prices.length - 1] 為第二次交易。
特定到i點(diǎn)時(shí)痢毒，可在i點(diǎn)把貨物賣出送矩，作為[0, i]區(qū)域的終結(jié)，然后再i點(diǎn)把貨物買入哪替， 作為[i, prices.length - 1]區(qū)域的開始栋荸，
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if not prices:
return 0
pre = []
low = float('inf')
res = 0
for i in xrange(len(prices)):
low = min(prices[i], low)
res = max(res, prices[i] - low)
pre.append(res)
high = float("-inf")
res = 0
post = []
total_max = 0
for i in xrange(len(prices)-1, -1, -1):
high = max(prices[i], high)
res = max(res, high - prices[i])
post.append(res)
total_max = max(total_max, pre[i] + res)
return total_max
