123. Best Time to Buy and Sell Stock III
AC的答案，基本的思想是，找出一个transaction在一个index之前完成可以获得的最大值，然后再找出，一个transaction在一个index之后完成可获得的最大值，只要找到这个index就可以了。但是这样做并不是DP，如果要解决at most k transaction好像这样就不行了。那道题在188，估计下周末能够做到。到时候再说。
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if len(prices) <= 1:
return 0
profit_from_left = [0 for _ in range(len(prices))]
profit_from_right = profit_from_left[:]
cur_min = prices[0]
for i in range(1, len(prices)):
profit_from_left[i] = max(0, prices[i] - cur_min, profit_from_left[i-1])
cur_min = min(cur_min, prices[i])
cur_max = prices[-1]
for i in range(len(prices)-1)[::-1]:
profit_from_right[i] = max(0, cur_max - prices[i], profit_from_right[i+1])
cur_max = max(cur_max, prices[i])
# print profit_from_left
# print profit_from_right
max_profit = 0
for index in range(len(prices)):
max_profit = max(profit_from_left[index]+profit_from_right[index], max_profit)
return max_profit
