买卖股票的最佳时机 III

买卖股票的最佳时机 III

读前福利，送大家一些电子书

123. 买卖股票的最佳时机 III

问题描述

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

分析问题

这个题目和上个题相比，状态又发生了变化，这里因为限制了交易次数，所以我们需要把交易次数的状态也保存起来。所以每天交易结束后，有5种状态。

1. 未进行过任何操作。

2. 只进行过一次买入操作。

3. 进行过一次买入和卖出操作。

4. 完成一笔的交易前提下，进行了第二次买入操作。

5. 完成两笔交易。

   由于第一个状态的利润为0，所以我们不需要记录。我们把剩下的4个状态分别用buy₁,sell₁,buy₂,sell₂来表示。下面我们来看一下如何根据前一天的状态，来通过转移方程生成今天的4个状态。

​ 对于buy₁而言，我们可以今天不操作，直接通过昨天的buy^′ ₁转移过来，或者我们从未进行过任何操作前提下，今天买入股票。

​ buy₁ =max(buy^′ ₁,-prices[i])

​ 对于sell₁而言，我们今天可以不做任何操作，直接通过昨天的sell^′ ₁转移过来，或者我们可以在只进行过一次买入交易的前提下，今天把股票卖出。

​ sell₁=max(sell^′ ₁,buy^′ ₁+prices[i]）

​ 对于buy₂而言，我们今天可以不做任何操作，直接通过昨天的buy^′ ₂转移过来，或者，我们在进行过一笔完成的交易条件下，今天再把该股票买入。

​ buy₂=max(buy^′ ₂,sell^′ ₁-prices[i]）

​ 对于sell₂而言，我们今天可以不做任何操作，直接通过昨天的sell^′ ₂ 转移过来，或者，我们在buy₂的前提下，今天把股票卖出。即

​ sell₂=max(sell^′ ₂,buy^′ ₂+prices[i]）

Tips:我们在计算sell1时，我们可以直接使用buy1而不是buy^′ ₁进行转移。buy1比buy^′ ₁多考虑的是在第i天买入股票的情况，而转移到sell1时，考虑的是在第i天卖出股票的情况，这样在同一天买入并且卖出股票的收益为0，不会对结果产生影响。对于buy2和sell2也是同样的考虑，我们可以直接用第i天求出的值来进行转移。

$$\begin{cases} buy1=max(buy1,-prices[i])\\ sell1=max(sell1,buy1+prices[i]\\buy2=max(buy2,sell1-price[i])\\sell2=max(sell2,buy2+prices[i]) \end{cases}$$

我们来看代码实现：

def maxProfit(prices):
    n = len(prices)
    #表示以prices[0]买入股票
    buy1=-prices[0]
    #表示在同一天买入并且卖出，即为0
    sell1=0
    #表示同一天买入卖出后再以prices[0]的价格买入
    buy2=-prices[0]
    #表示同一天买入卖出两次，即为0
    sell2 = 0
    for i in range(1, n):
        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

prices=[7, 1, 5, 3, 6, 4]
print(maxProfit(prices))