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 (i.e., you must sell the stock before you buy again).
Example 1:
Input: [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.
Example 2:
Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
engaging multiple transactions at the same time. You must sell before buying again.
Example 3:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
Solution1:
class Solution:（TLE）
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if len(prices)<=2:
return self.maxProfit1(prices)
profit = 0
for i in range(len(prices)):
profit = max(profit,self.maxProfit1(prices[:i]) + self.maxProfit1(prices[i-1:]))
return profit
def maxProfit1(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if len(prices)<1:
return 0
little,profit = prices[0],0
for i in range(1,len(prices)):
temp = prices[i] - little
profit = max(profit,temp)
little = min(little,prices[i])
return profit
调用121中的solution，将原list分成两段分别调用。
Solution2:
class Solution:
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if len(prices)<=1:
return 0
pre = [0 for i in range(len(prices))]
post = [0 for i in range(len(prices))]
minprice = prices[0]
maxprice = prices[-1]
for i in range(1,len(prices)):
pre[i] = max(pre[i-1],prices[i]-minprice)
minprice = min(prices[i],minprice)
for i in range(len(prices)-2,-1,-1):
post[i] = max(post[i+1],maxprice-prices[i])
maxprice = max(prices[i],maxprice)
res = 0
for i in range(len(prices)):
res = max(res,pre[i]+post[i])
return res
采用两个数组。
一个保存前i天的最大收益，从前向后遍历可以得到。
一个保存后i天的最大收益，从后向前遍历可以得到。
Solution3：
class Solution:
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
sell1,sell2,buy1,buy2 = 0,0,-100000,-100000
for i in range(len(prices)):
buy1 = max(buy1,-prices[i])
sell1 = max(sell1,buy1+prices[i])
buy2 = max(buy2,sell1-prices[i])
sell2 = max(sell2,buy2+prices[i])
return sell2
核心是假设手上最开始只有0元钱，那么如果买入股票的价格为price，手上的钱需要减去这个price，如果卖出股票的价格为price，手上的钱需要加上这个price。
它定义了4个状态：
Buy1[i]表示前i天做第一笔交易买入股票后剩下的最多的钱；
Sell1[i]表示前i天做第一笔交易卖出股票后剩下的最多的钱；
Buy2[i]表示前i天做第二笔交易买入股票后剩下的最多的钱；
Sell2[i]表示前i天做第二笔交易卖出股票后剩下的最多的钱；
那么
Buy1[i]=max{Buy[i-1],-prices[i]}
Sell1[i]=max{Sell[i-1],Buy1[i-1]+prices[i]}
Buy2[i]=max{Buy2[i-1],Sell[i-1]-prices[i]}
Sell2[i]=max{Sell2[i-1],Buy2[i-1]+prices[i]}
可以发现上面四个状态都是只与前一个状态有关，所以可以不使用数组而是使用变量来存储即可。
参考自：https://blog.csdn.net/u012501459/article/details/46514309