程序人生|漫画：程序教你寻找股票买入卖出的最佳时机（动态规划）

本文插图
作者 | 小灰
来源 | 程序员小灰（ID：chengxuyuanxiaohui）
【程序人生|漫画：程序教你寻找股票买入卖出的最佳时机（动态规划）】

本文插图
前一段时间，我们介绍了一个经典算法题目：寻找股票买入卖出的最佳时机。这个题目看似简单，却有着许多种变化。
在上一篇中，我们讲解了最多1次买卖和无限次买卖的解法，那么，如果只允许最多2次股票买卖，如何寻找最佳时机呢？

本文插图

本文插图

本文插图

本文插图
我们仍然以之前的数组为例：

本文插图
首先，寻找到1次买卖限制下的最佳买入卖出点：

本文插图
两次买卖的位置是不可能交叉的，所以我们找到第1次买卖位置后，把这一对买入卖出点以及它们中间的元素全部剔除掉：

本文插图
接下来，我们按照同样的思路，再从剩下的元素中寻找第2次买卖的最佳买入卖出点：

本文插图
这样一来，我们就找到了最多2次买卖情况下的最佳选择：

本文插图

本文插图

本文插图

本文插图

本文插图

本文插图
对于上图的这个数组，如果独立两次求解，得到的最佳买入卖出点分别是【1,9】和【6,7】，最大收益是（9-1）+（7-6）=9：

本文插图
但实际上，如果选择【1,8】和【3,9】，最大收益是（8-1）+（9-3）=13>9：