LeetCode0123.BestTimetoBuyingandSellStockIII买卖股票的最佳时机III【Hard】【Python】【动态规划】ProblemLeetanArrayforwhichyouhaveanCodeSay第i个元素是给定股票在第i天的价格。设计一个算法来找到最大利润。您最多可以完成两笔交易。注意：您不能同时进行多笔交易（即，您必须在再次购买之前卖出股票）。示例1：输入：[3,3,5,0,0,3,1,4]输出：6解释：在第4天买入（价格=0）并在第6天卖出（价格=3），利润=3-0=3。然后在第7天买入（价格=1）并且第8天卖出（价格=4），利润=4-1=3。示例2：输入：[1,2,3,4,5]输出：4解释：第1天买入（价格=1）并卖出第5天（价格=5），利润=5-1=4。请注意，您不能在第1天买入，在第2天买入，然后再卖出，因为您同时进行多项交易。你必须先卖后买再次。示例3：输入：[7,6,4,3,1]输出：0解释：在这种情况下，没有交易完成，即最大利润=0。问题给定一个数组，它的第i个元素是第i天给定股票的价格设计一个算法来计算您可以获得的最大利润。您最多可以完成两笔交易。注意：您不能同时参与多笔交易（必须先卖出之前的股票再买入）。示例1：输入：[3,3,5,0,0,3,1,4]输出：6解释：第4天买入（股价=0），第6天买入（股价=3）卖出时,这笔交易可以盈利=3-0=3。那么，第7天买入（股价=1），第8天卖出（股价=4），这笔交易可以盈利=4-1=3。示例2：输入：[1,2,3,4,5]输出：4解释：第1天买入（股价=1），第5天卖出（股价=5），本次交易可获利=5-1=4。请注意，您不能在第1天和第2天连续买入股票，然后再卖出。因为这是同时涉及多笔交易，所以必须先卖掉之前的股票再买。示例3：输入：[7,6,4,3,1]输出：0解释：在这种情况下，没有交易完成，因此最大利润为0。思路动态规划求状态方程dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k][1]+prices[i])解释：昨天没有股票，但是有昨天卖出的股票dp[i][k][1]=max(dp[i-1][k][1],dp[i-1][k][0]-prices[i])解释：有昨天有股票，昨天没有股票。今天购买的基本情况：dp[-1][k][0]=dp[i][k][0]=0dp[-1][k][1]=dp[i][k][1]=-infk=2因为k是2，所以k一定是穷尽的。dp[i][2][0]=max(dp[i-1][2][0],dp[i-1][2][1]+价格[i])dp[i][2][1]=max(dp[i-1][2][1],dp[i-1][1][0]-价格[i])dp[i][1][0]=max(dp[i-1][1][0],dp[i-1][1][1]+价格[i])dp[i][1][1]=max(dp[i-1][1][1],-prices[i])i=0时，dp[i-1]不合法。dp[0][1][0]=max(dp[-1][1][0],dp[-1][1][1]+prices[i])=max(0,-infinity+价格[i])=0dp[0][1][1]=max(dp[-1][1][1],dp[-1][1][0]-价格[i])=max(-infinity,0-prices[i])=-prices[i]dp[0][2][0]=max(dp[-1][2][0],dp[-1][2][1]+价格[i])=max(0,-infinity+prices[i])=0dp[0][2][1]=max(dp[-1][2][1],dp[-1][2][0]-prices[i])=max(-infinity,0-prices[i])=-prices[i]空间复杂度：O(1)Python3代码类解决方案：defmaxProfit(self,prices:List[int])->int:dp_i_2_0,dp_i_1_0=0,0#dp_i_2_1,dp_i_1_1=-prices[0],-prices[0]#会报错：listindexoutofrangedp_i_2_1,dp_i_1_1=float('-inf'),float('-inf')#Negativeinfinityforiinrange(len(prices)):#昨天没有库存，但昨天有库存，今天卖出dp_i_2_0=max(dp_i_2_0,dp_i_2_1+prices[i])#昨天有库存，昨天没有库存。今天购买dp_i_2_1=max(dp_i_2_1,dp_i_1_0-prices[i])#昨天没货，昨天有货，今天卖dp_i_1_0=max(dp_i_1_0,dp_i_1_1+prices[i])#昨天有货，昨天没货，今天买dp_i_1_1=max(dp_i_1_1,-prices[i])returndp_i_2_0codeAddressGitHublinkreferenceOnemethodkill6库存问题
