题目大意: 给定一支股票每天的价格,求最佳的买入、卖出时机。最多可以完成两笔交易。
题目分析: 这是一道动态规划题。定义四个变量,buy1, sell1, buy2, sell2。 遍历价格数组中的每个值,buy1记录,截止到这一天,第一次买入后的最大收益(用价格的相反数代表买入带来的收益,因为买入是需要花钱的);sell1记录截止到这一天,第一次买出后的最大收益。
代码(Python3):
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices or len(prices) == 0:
return 0
else:
buy1 = -1 * prices[0]
buy2 = -1 * prices[0]
sell1 = 0
sell2 = 0
for i in range(1, len(prices)):
sell2 = max(prices[i] + buy2, sell2)
buy2 = max(sell1 - prices[i], buy2)
sell1 = max(prices[i] + buy1, sell1)
buy1 = max(prices[i] * -1, buy1)
return sell2
需要注意一点:
每次更新变量的时候,需要先更新靠后的操作,再更新靠前的操作。(先后顺序分别为:buy1、sell1、buy2、sell2)。这是因为题目要求“不能同时参与多笔交易”,以sell1为例,更新它时,只能依赖于今天之前得到的buy2值。