123. Best Time to Buy and Sell Stock III
AC的答案，基本的思想是傻铣，找出一個(gè)transaction在一個(gè)index之前完成可以獲得的最大值，然后再找出卵渴，一個(gè)transaction在一個(gè)index之后完成可獲得的最大值兑障，只要找到這個(gè)index就可以了。但是這樣做并不是DP登淘，如果要解決at most k transaction好像這樣就不行了箫老。那道題在188，估計(jì)下周末能夠做到黔州。到時(shí)候再說(shuō)耍鬓。
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
