这个问题都出到 III 了，真是无穷无尽啊。参考 [Best Time to Buy and Sell Stock II](../005. Best Time to Buy and Sell Stock II) 与 [Best Time to Buy and Sell Stock](../039. Best Time to Buy and Sell Stock).
这道题从 I 里要求的仅有一次交易，转变为最多可以进行两次交易。那么很自然地，我们还是从一次交易的思路着手。
6 1 3 2 4 7 6 10 15
low: 6 1 1 1 1 1 1 1 1
ret: 0 0 2 2 3 6 6 9 14
^
查看一下 I 中的思路，我们运用了两个变量来完成此事，low 时刻记录最低股价，ret 则不断刷新差价，前者求 min, 后者求 max. 想在反思这种解法，实际上是非常朴素的 DP, 也是一种积累思想的体现。
如果再给我们一次机会，再来一次交易呢？就看上述例子，我们一眼就瞧出了两次交易转手的地方：
6 1 3 2 4 7 6 10 15
low: 6 1 1 1 1 1 1 1 1
ret: 0 0 2 2 3 6 6 9 14
^ ^
6+9 = 15 ---> ret
如果在 7 的时候卖，6 的时候买，那么竟然可以得到 15 的差价。反思一下，我们人脑是如何判别出这个点的。显然，我们可以发现，在 1~15 这个序列里，出现下降趋势的地方仅有两处：3->2, 7->6, 前者我们最终获得的差价也是 15(2+13)。而想要获得最大的差价，需这种下降的地方，下降的更多才是。这里 3-2 == 7-6 == 1. 所以第二次交易至多也只能增加 1.
在 I 里，我们采用了 low + ret 来捕获上升趋势时的变化。而根据上述分析，我们显然还对下降趋势的地方感兴趣。但这个下降有个条件，即一定要是在总的上升趋势中的小下降。那么从头开始捕获就不太合理，从尾部开始，或许可以。相似的，我们采用 high + ret 来计算。
6 1 3 2 4 7 6 10 15
ret: 0 0 2 2 3 6 6 9 14
15 15 15 15 15 15 15 15 15 :high
15 15 15 15 15 15 15 14 14 :new_ret
high 与 low 一样，始终记录最高股价，new_ret 则不断刷新差价。此时的 new_ret == ret + high - today. 显然，这一次两者都是求 max 了。
还可以发现的是，上一次迭代每一次 ret 都是对我们这一次的逆向迭代有用的，所以我们最终还是需要 O(n) 的缓存空间。
总结一下，两次迭代，用 vector 记录历史差价。最终得到的 ret 即为所求。AC.