![Pure Soul](https://oo2ee.com/"wp-content/uploads"/2021/12/cropped-cropped-logo-1.png){kind=logo}
买卖股票的最佳时机是经典的动态规划问题，即使它有一些取巧的办法(这些“办法”也是DP做法的优化版本)。
目录
简单版本
简单版本：给定一个数组，它的第i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
题意理解
题意不难理解，就是选出一个股价最低点和股价的最高点进行交易，同时最低价的日期应该早于最高价。
超时做法(针对Python而言)
从前往后开始遍历，使用maxProfit记录遍历到当前第i个股价时的获取的最大利润，如果遍历下一个股价时获取的最大利润大于maxProfit，那么进行替代。而获得maxProfit的方法则是，使用prices[i]-min(prices[:i])，这种方法在小数据集上可以通过，数据集过大时会出现超时。此方法的时间复杂度为O(0+1+2+…+n-1)=O(n^2)，不使用额外空间，空间复杂度为O(1)。
from typing import List
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# 超时算法
if len(prices)==1: return 0
maxPrices=0
for i in range(1,len(prices)):
maxPrices=max(maxPrices,prices[i]-min(prices[0:i]))
return maxPrices
改进超时算法
上面的min(prices[:i])其实不用每次遍历过程当中都进行求解，我们使用额外的一个变量lowerPrices来记录min(prices[:i])，那么lowerPrices=min(lowerPrices,prices[i])表示min(prices[:i])。改进之后，时间复杂度为O(n)，不使用额外线性空间，空间复杂度为O(1)。
代码如下：
from typing import List
class Solution:
def maxProfit1(self, prices: List[int]) -> int:
# 改进超时算法
if len(prices)==1: return 0
maxPrices=0
lowerPrices=1e10
for i in range(1,len(prices)):
lowerPrices=min(prices[i],lowerPrices)
maxPrices=max(maxPrices,prices[i]-lowerPrices)
return maxPrices
简单版本(多次交易)
多次股票交易
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 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做法
DP的重点是考虑如何选取状态，以及如何对状态进行转移
对于这个问题，可以选择第i天获取的最大利润作为dp[i]，那么dp[i]和dp[i-1]的关系如何表示呢？如果在第i天没有股票，那么第i天可以买入，此时dp[i]=dp[i-1]-prices[i]，同时如果在第i天持有股票，那么第i天可以卖出。此时dp[i]=dp[i-1]+prices[i]。因此dp可以使用一个二维数组进行表示dp[0][i]表示第i天不持有股票，dp[1][i]表示第i天持有股票。
dp[0][i]=max(dp[1][i-1]+prices[i],dp[0][i-1])
#第i天不持有股票的最大利润为把前一天持有的股票售卖，或者保持前一天的状态
dp[1][i]=max(dp[0][i-1]-prices[i],dp[1][i-1])
#第i天持有股票的情况下的最大利润为买入当天的股票，或者保持前一天的状态
此方法的时间复杂度为O(n),同时需要辅助空间，那么空间复杂度为O(n)，代码为：
from typing import List
class Solution:
def maxProfitDP(self,prices: List[int]) -> int:
# 动态规划算法
# dp[i][0]和dp[i][1]分别表示第i天持有不持有股票的收益
# dp[i][0]=max(dp[i-1][0], dp[i-1][1]+prices[i])
# dp[i][1]=max(dp[i-1][1], dp[i-1][0]-prices[i])
# 特殊情况dp[0][0]=0,dp[0][1]=-prices[0]
dp=[[0]*len(prices),[-prices[0]]*len(prices)]
for i in range(1,len(prices)):
dp[0][i] = max(dp[0][i-1], dp[1][i-1] + prices[i])
dp[1][i] = max(dp[1][i - 1], dp[0][i - 1] - prices[i])
return max(dp[0][-1],dp[1][-1])
改进DP做法
通过上面的代码可以看出，其实无需维护整个dp表，毕竟dp[i]只和dp[i-1]以及prices[i]有关，因此只采用两个变量来维护即可。此时时间复杂度为O(n),同时需要辅助空间，那么空间复杂度为O(1)。
from typing import List
class Solution:
def maxProfitDPOpt(self, prices: List[int]) -> int:
# 动态规划算法
# dp[i][0]和dp[i][1]分别表示第i天持有不持有股票的收益
# dp[i][0]=max(dp[i-1][0], dp[i-1][1]+prices[i])
# dp[i][1]=max(dp[i-1][1], dp[i-1][0]-prices[i])
# 特殊情况dp[0][0]=0,dp[0][1]=-prices[0]
# 无需维护数组，仅仅只维护两个值
dp = [[0] * len(prices), [-prices[0]] * len(prices)]
dp_none,dp_have=0,-prices[0]
for i in range(1, len(prices)):
dp_none_tmp = max(dp_none, dp_have + prices[i])
dp_have_tmp = max(dp_have, dp_none - prices[i])
dp_none,dp_have=dp_none_tmp,dp_have_tmp
return max(dp_none,dp_have)
取巧做法
如果需要最大利润，那么只要明天的股价高于今天的股价，那么就可以今天买明天卖(虽然本质上来说不会在今天知道明天的股价的)
from typing import List
class Solution:
def maxProfit(self, prices: List[int]) -> int:
sum=0
for i in range(len(prices)-1):
if prices[i+1]>prices[i]:
sum+=prices[i+1]-prices[i]
return sum
中等版本(含手续费)
中等版本
给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
示例 1:
输入: prices = [1, 3, 2, 8, 4, 9], fee = 2
输出: 8
解释: 能够达到的最大利润:
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
题意理解
包含手续费的解法其实就是在之前不包含手续的基础上增加一个额外的因素，DP的转移方程是不变的
dp[0][i]=max(dp[1][i-1]+prices[i]-fee,dp[0][i-1])
#第i天不持有股票的最大利润为把前一天持有的股票售卖，或者保持前一天的状态，同时增加手续费的影响，买卖只需要付一次交易费用，规定在卖出的时候付手续费
dp[1][i]=max(dp[0][i-1]-prices[i],dp[1][i-1])
#第i天持有股票的情况下的最大利润为买入当天的股票，或者保持前一天的状态，同时增加手续费的影响
DP的解法
from typing import List
class Solution:
def maxProfitDPOpt(self, prices: List[int], fee: int) -> int:
# 动态规划算法
# dp[i][0]和dp[i][1]分别表示第i天持有不持有股票的收益
# dp[i][0]=max(dp[i-1][0], dp[i-1][1]+prices[i])
# dp[i][1]=max(dp[i-1][1], dp[i-1][0]-prices[i])
# 特殊情况dp[0][0]=0,dp[0][1]=-prices[0]
# 无需维护数组，仅仅只维护两个值
dp_none,dp_have=0,-prices[0]
for i in range(1, len(prices)):
dp_none_tmp = max(dp_none, dp_have + prices[i]-fee)
dp_have_tmp = max(dp_have, dp_none - prices[i])
dp_none,dp_have=dp_none_tmp,dp_have_tmp
return max(dp_none,dp_have)
困难版本(只能交易两次)
困难版本：
给定一个数组，它的第i个元素是一支给定的股票在第i天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例1:
输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
示例 2：
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出.因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这个情况下, 没有交易完成, 所以最大利润为 0。
示例 4：
输入：prices = [1]
输出：0
题意理解
相比于简单版本的交易一次而言，这题的限制了两次交易（并且两次交易不能重合：第一次的每卖出之前不能买入第二只股票），那么很简答的想法就是对简单题进行改进。把给定的区间分成依次分为两半，求每一半的最大利润最后把两部分最大利润相加就是最后的结果。
借助简单题的解法
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# 超时做法，将区间分为两个子区间分别进行计算
if len(prices)==1: return 0
chargeSig=self.maxProfitSig(prices) #单次交易能获得的最大利润
chargeDouble=0
for i in range(2,len(prices)-1):
chargeDouble=max(self.maxProfitSig(prices[:i])+self.maxProfitSig(prices[i:]),chargeDouble)
return max(chargeDouble,chargeSig)
def maxProfitSig(self, prices: List[int]) -> int:
# 只进行单次交易所能达到的最大利润
min_price_befor=prices[0]
max_profit=0
for price in prices:
max_profit=max(max_profit,price-min_price_befor)
min_price_befor=min(price,min_price_befor)
return max_profit
值得注意的是，这种做法的Python版本提交会超时(C++不会，Python还是菜鸡了一点)。并且题目要求的最多只能两次交易，因此需要先求交易一次的最大利润，最后进行比较。对时间复杂度进行分析的话就是：先求的只交易一次的时间复杂度为O(n)，之后对每一次的两部分进行求解最大利润的时间复杂度有O(p)+O(q)其中p+q=n，那么一次的时间复杂度依旧为O(n)，同时需要对数组进行遍历，那么最后总的时间复杂度为O(n)+O(n^2)=O(n^2)。
显然O(n^2)的时间复杂度不能满足要求，那么如何改进呢？在第i天的最大利润可以表示为profit[i]=profit_brfor[i]+profit_behind[i]，其中profit_befor[i]表示[0:i]天的利润，profit_behind[i]表示[i:len(prices)-1]天的利润，把两个阶段利润相加就是以第i天作为分界线的最大利润。如果能够分别在O(n)的时间复杂度内求出profit_befor[i], i=0...len(prices)-1以及profit_behind[i], i=0...len(prices)-1，那么时间复杂度就可以简化。其中正着求profit_befor[i]已经实现了：
def maxProfit_befor(self,prices: List[int]) -> List[int]:
max_profit=[0]*len(prices)
min_price=prices[0]
for i in range(1,len(prices)):
max_profit[i] = max(prices[i] - min_price, max_profit[i-1])
min_price=min(prices[i],min_price)
return max_profit
那么怎么反过来求profit_behind[i]呢？其实只需要把其中的最大最小关系搞清楚就行。
def maxProfit_behind(self,prices: List[int]) -> List[int]:
max_profit=[0]*len(prices)
max_price=prices[-1]
for i in range(len(prices)-2,-1,-1):
max_profit[i]=max(max_profit[i+1],max_price-prices[i])
max_price=max(max_price,prices[i])
return max_profit
最后的代码优化结果为：
class Solution:
def maxProfit(self, prices: List[int]) -> int:
max_profit_befor=self.maxProfit_befor(prices)
max_profit_behind=self.maxProfit_behind(prices)
return max([x+y for x,y in zip(max_profit_befor,max_profit_behind)])
def maxProfit_befor(self,prices: List[int]) -> List[int]:
max_profit=[0]*len(prices)
min_price=prices[0]
for i in range(1,len(prices)):
max_profit[i] = max(prices[i] - min_price, max_profit[i-1])
min_price=min(prices[i],min_price)
return max_profit
def maxProfit_behind(self,prices: List[int]) -> List[int]:
max_profit=[0]*len(prices)
max_price=prices[-1]
for i in range(len(prices)-2,-1,-1):
max_profit[i]=max(max_profit[i+1],max_price-prices[i])
max_price=max(max_price,prices[i])
return max_profit