Python每日一练-----买卖股票的最佳时机Ⅲ
⛅（day18）
目录
🖍题目：
题目分析：
解题思路：
🌈动态规划解法
✏代码注释
🖍题目：
给定一个数组，它的第 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
题目分析：
题目要求找出在最多进行两次交易的情况下获得的利润最大值，这意味着我们可以进行一次交易，也可以进行两次交易。但是手中持有股票时必须先出售才能进行第二次购买。
解题思路：
动态规划解法
进行动态规划五部曲
✨1.分析确定dp数组以及其下标的含义或状态分析
这里不用dp数组，进行状态分析在第i天结束后，有下面5个状态
（1）不买也不卖
（2）进行了一次买进股票
（3）进行了一次买进和一次抛售（完成第一次交易）
（4）在完成第一次交易的前提下，进行第二次买进
（5）在完成第一次交易的前提下，完成第二次交易
注意：这些操作的最后一步并不一定是在第i天完成
✨2.确定递推公式
由上面的状态分析可知。
状态（1） 无利润产生为0（可以舍去）
状态（2）first_buy_profit
获得的利润 = max（day_before_profit, -prices[i]）
其中day_befor_frofit表示前些天获得的总利润，-prices[i]表示第i天购进股票的开销
为什么状态（2）获取到的利润不是= -prices[1]，状态（2）不是只有买进操作吗？
这里要注意，状态（2）虽然只有买进操作，但是这一次的买进操作可能在第i天前，比如第i-1天，第i-2天等等，不妨设在第i-2天买进，那么由状态（2）：第i天结束后只进行一次买进操作（发生在第i-2天），这时候第i天获得的最大利润就等于 = max（day_before_profit, -prices[i]）
对于状态（2）获得的利润为什么是= max（day_befor_profit, -prices[i]），-prices是负数，day_befor_profit不是一定>=-prices吗？
准确的说-prices不一定是负数可能是0，因为例子中有股价等于0的情况（虽然这个股价等于零的情况很离谱，但是做题也要依照题意），如果股价等于0，而day_before获得的利润为负数，此时-prices > day_before_profit，所以day_befor_profit不一定>=-prices。
状态（3）first_sell_profit
在状态（2）的基础上
获得的最大利润 = max（day_before_profit, first_buy_profit + prices[i])
其中day_befor表示前些天获得的总利润，+prices[i]表示第i天抛售的收入
状态（4）second_buy_profit
在状态（3）的基础上
获得的最大利润 = max（day_beforre_profit, first_sell_profit - prices[i])
其中day_befor_frofit表示前些天获得的总利润，-prices[i]表示第i天购进股票的开销
状态（5）second_sell_profit
在状态（4）的基础上
获得的最大利润 = max（day_before_profit, second_buy_profit + prices[i])
其中day_befor表示前些天获得的总利润，+prices[i]表示第i天抛售的收入
最后的递推公式为
first_buy_profit = max（first_buy_profit, -prices[i]）
first_sell_profit = max（first_sell_profit, first_buy_profit + prices[i])
second_buy_profit = max（second_buy_profit, first_sell_profit - prices[i])
second_sell_profit = max（second_sell_profit , second_buy_profit + prices[i])
最后的递推公式将day_before_profit全部转化为了对应的first_buy_profit，first_sell_profit，
second_buy_profit，second_sell_profit。它们和day_before_profit的区别在于，它们包含了状态最后一步可能发生在第i天，而day_before_profit则不包含。
✨3.如何初始化dp数组
由递推公式可知，递推公式的基础为，
first_buy_profit，first_sell_profit，second_buy_profit，second_sell_profit
初始化
first_buy_profit = second_buy_profit = -prices [0]
first_sell_profit = second_sell_profit = 0
初始化first_buy_profit = -prices [0] 好理解，但是其他基础这样初始化的依据是什么呢？
对于初始化我们要考虑边界条件，对于第0天：
- second_buy_profit为第2次购买，这时由在第0天进行第一次交易（买了又卖利润为0），然后又进行一次购买花费prices[i]。所以second_buy_profit = 0 +（-prices[0]）= - prices[0]
- first_sell_profit为第一次出售，之前先进行了一次购买，因为在都是在第0天进行，所以first_sell_profit = 0
- second_sell_profit为第二次购买，在第0天进行第一次交易（买了又卖利润为0），然后又进行一次购买花费prices[0]又卖出，获得prices[0]所以second_sell_profit = 0
✨4.确定遍历的顺序
根据递归公式，遍历顺序为从头到尾。
✨5.举例验证推导的dp数组（公式）是否正确
可以带入一个简单以的例子，比如例2.
那么最终的答案是什么呢？
可以肯定的是最终答案在first_sell_profit，second_sell_profit中，因为抛售后获得的利润一定会比将股票留在手里获得的利润高。
又因为上面分析到，可以在同一天买了又卖掉，所以当出现完成一次交易为最优解的情况时（如例4），first_sell_profit可以理解成在完成这一次交易后，又在当天（同一天）买了又卖掉，这不影响最终结果。所以second_sell_profit为最终结果。
代码实现
🌈动态规划解法
def maxProfit(prices): first_buy_profit = second_buy_profit = -prices[0] first_sell_profit = second_sell_profit = 0 for i in range(1, len(prices)): first_buy_profit = max(first_buy_profit, -prices[i]) first_sell_profit = max(first_sell_profit, first_buy_profit+ prices[i]) second_buy_profit = max(second_buy_profit, first_sell_profit - prices[i]) second_sell_profit = max(second_sell_profit, second_buy_profit + prices[i]) return second_sell_profit✏代码注释
def maxProfit(prices): # 初始化递归基础 first_buy_profit = second_buy_profit = -prices[0] first_sell_profit = second_sell_profit = 0 # 运行递归公式，因为第0天已在初始化中讨论，所以i从1开始 for i in range(1, len(prices)): first_buy_profit = max(first_buy_profit, -prices[i]) first_sell_profit = max(first_sell_profit, first_buy_profit + prices[i]) second_buy_profit = max(second_buy_profit, first_sell_profit - prices[i]) second_sell_profit = max(second_sell_profit, second_buy_profit + prices[i]) return second_sell_profit # 返回结果一位程序需要遍历一次数组所以时间复杂度为O(n)，只需四个状态储存运行，空间复杂度O(1).
今天就到这，明天见。🚀
❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄end❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄