本次刷题日记的第 89 篇，力扣题为：123. 买卖股票的最佳时机 III
一、题目描述：
咱们继续来做买卖股票，咱们干到底，看看能不能假装学会买股票
二、这道题考察了什么思想？你的思路是什么？
还是同样的买卖股票的题目，官方的要求总是变幻莫测，我们也只能努力去满足对方的需求，正如客户的需求一般捉摸不定
这一次，买卖股票正和我们上次说到的，开始限定买卖股票的次数了，而不是任意买卖多次了，因此，还是那句话，咱们计算最大利润的话，就不能使用贪心算法了，因为这一次题目还限定了我们最多只能交易 2 次 ， 并且要求我们同一时间只能有一只股票买入或者卖出，且在此购买前，必须要卖掉之前的股票
分析
那这个时候我们来思考这道题呢，显然上面我们说了光使用贪心的方式肯定不行了，我们必须要另寻他法
咱们仔细来看一下，对于每一天，我们买还是卖，对于第二天的影响是什么，对于每一天结束之后，我们可以总结一下，今天都干了啥，以及第二天可以干啥，例如今天结束了，我们会有这些状态
- a 没有进行过任何操作，不买也不卖
- b 只进行过一次买操作
- c 进行了一次买操作和一次卖操作，那么就是完成了一笔交易
- d 在完成了一笔交易的前提下，进行了第二次买操作
- e 完成了全部两笔交易
那么如果是第 a 种状态，我们利润肯定是 0 ，如果是 第 b 种状态，目前来看我们的利润肯定是负数，那么 第 c ，第 d ，第 e 种状态就需要咱们根据前面每一天的状态来推导了
例如，我们可以这样来推导
对于状态 b，那么我们前一天可以是未操作，今天咱们买了一手 则 状态就是 -price[i] ，也可以是前一天买了一手，今天未操作，那么状态就是前一天的 b 的状态
b=max(b,−price[i])b = max(b, -price[i])b=max(b,−price[i])
同理，c 状态的话，咱们可以是今天保持没做任务操作，则状态还是 c，我们也可以是在买了一手的前提下，今天卖出股票了，则状态就是 进行了一次操作然后加上今天的卖出操作，则状态为 b+price[i]
c=max(c,b+price[i])c = max(c, b+price[i])c=max(c,b+price[i])
同理，d 状态的时候，我们也可以不进行任何操作，状态就是还是 d，我们也可以今天进行买操作，则就是在完成了一笔交易的状态下又进行了 1 比买操作，则状态是 c-price[i]
d=max(d,c−price[i])d = max(d, c-price[i])d=max(d,c−price[i])
同理，对于 e 状态，我们还是可以选择不操作，则状态是 e，我们也可以卖出股票，则状态是建立在 d 的操作卖出了股票，则状态是 d+price[i]
e=max(e,d+price[i])e = max(e, d+price[i])e=max(e,d+price[i])
那么，其实我们光看这几个状态可能有明确的答案，但是我们根据时间推移，去偏移数组，我们就可以得到最终的 e 状态的结果了
来一起手撸代码吧
三、编码
根据上述逻辑和分析，我们就可以翻译成如下代码
- 对于现在的我们来说，根据状态方程来实现代码就可以了，完全按照上述提供的状态方程来进行实现即可
编码如下：
func maxProfit(prices []int) int { b, c := -prices[0], 0 d, e := -prices[0], 0 for i := 1; i < len(prices); i++ { b = max(b, -prices[i]) c = max(c, b+prices[i]) d = max(d, c-prices[i]) e = max(e, d+prices[i]) } return e } func max(a, b int) int { if a > b { return a } return b }
四、总结：
按照咱们这种做法，其实最重要的就是需要找到每一天的各种状态，然后去推导接下来剩下天的状态，后一天的状态始终会被前一天的状态所影响，我们工作的时候，也要注意这种状态，不要总是被过去的自己影响到
这么来看，我们只对数组做了一次遍历，因此时间复杂度是O(n) ，很明确，我们没有引入额外的空间消耗，因此咱们的空间复杂度是 O(1)
原题地址：123. 买卖股票的最佳时机 III
欢迎点赞，关注，收藏
朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力
好了，本次就到这里
技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。
我是阿兵云原生，欢迎点赞关注收藏，下次见~
