买卖利润最大的股票

这篇帖子延续了关于算法思维解决一个众所周知的问题的讨论，这个问题被称为买卖股票的最佳时间。

这个问题的解决很难，我不认为它是一个很好的面试问题，但它仍然是一个很好的练习，可能需要一个中级开发人员几个小时才能解决。

为了获得最大值，在阅读解决方案之前，您应该分配足够的时间来尝试以有效的方式解决它。

我们得到了一个代表股票价格的整数列表；我们必须找出假设至多两个没有重叠的买入-卖出交易的情况下可以获得的最大利润。

乍一看，问题看起来很简单；我们很快就会看到事实并非如此！

思考这个问题，我们可以看到存在三种“类型”的解决方案：

将此方法转换为按2点和4点创建所有配对并返回最大利润的函数非常简单：

为了简化性能测试，让我们创建一个函数来返回一个随机价格序列，并针对不同大小的输入运行get_max_Profit函数：

请注意，20个点的序列需要几毫秒，但当我们增加到200点时，我们很快就会达到13秒以上。

之所以会出现这种情况，是因为我们的解决方案非常慢；请注意，我们计算的是从价格中取2点和4点的所有可能的对，这意味着所需的利润计算次数由以下公式给出：

很明显，我们需要一个更聪明的解决方案，使我们能够以更有效的方式解决这个问题。

随着我们更深入地思考问题，我们意识到，对于价格曲线中的每个数据点，我们都有一个从左到右的最大利润交易，这意味着如果我们迭代所有的点并存储所有的总和(只计算正值)，它们的最大值将是所需的值。

在这种情况下，我们的解决方案的复杂性将与数组的大小乘以在曲线左右两侧查找较大事务的成本成正比。

要尝试这种方法，我们需要创建一个函数，该函数将接收一段价格并为其返回最大可能的利润。不过，重要的是，我们希望避免像以前那样创建所有可能的配对，并将查找最大利润交易的过程减少为每个分区的一次传递。经过一番思考，我们最终得到了以下解决方案：

请注意，计算最大利润现在是0.16，与我们以前得到的13.29相比，看起来有了很大的改进，但我们还有更多的工作要做。

虽然比以前快得多，但随着曲线大小的增长，该函数会迅速减慢。

在我们继续前进并尝试改进我们的解决方案之前，了解我们当前基于两个基本概念的解决方案将会很有帮助：

我们可以通过迭代所有点并比较它们的左右总和来计算最大利润。

计算分部最大利润的算法很有趣，所以让我们仔细研究一下。

计算子序列的最大利润交易是我们解决方案的核心，我们需要很好地消化它，以便理解问题的解决方案。

根据价格顺序[8，12，1，9，6，11]，很容易得出结论，可以获得的最大利润是10(在第三个点买入，在第十个点卖出)：

为了找出这一利润，我们需要迭代整个曲线，并在每个点“记住”我们到目前为止看到的最低和最高价格。更重要的是，我们需要确保最低价格出现在最高价格之前；这就是该算法有点棘手的地方。

当我们继续前进(向右)时，如果我们发现一个新的最低价格，我们将存储的较低值重新初始化为新的值，并将最大值设置为零，否则，如果我们已经达到一个新的较大值，我们将用它替换到目前为止的较大值。

此时，如果我们将当前利润与之前的利润进行比较，则可以很容易地计算任何迭代点的较大利润，这正是此代码正在执行的操作：

因为我们迭代传递给函数的所有价格，所以其复杂度为O(M)(m是传入数组的长度)。

如前所述，要计算零个、一个或两个交易的最大可能利润，我们需要迭代整个价格序列(长度为n)，并为每个点调用左侧和右侧的Brutal_find_max_Delta函数。请注意，对于每个点，复杂度将是：O(M)+O(n-m)或O(N)。

因此，虽然这种方法与以前的解决方案相比有了改进，但仍然很慢，需要进一步改进。

在我们的解决方案中，我们注意到真正“昂贵”的是左右最大值的计算；这使我们思考是否可以通过重用一些已经计算的数据来简化他们的计算。我们的方法是创建一个新的列表，其长度与传入的价目表相同，其中每个点都将具有左侧的最大利润。

这样做似乎很容易更改brtal_find_max_delta值以跟踪每个点的最大值：

只需简单修改left_side_max_deltas，我们就可以编写一个类似的函数来计算点右侧的最大值：

其中，每个数据点表示可在其右侧找到的最大区域，如下图所示：

既然我们已经准备好从左到右的最大利润曲线创建函数，我们就可以编写一个函数来解决这个问题：

我们的解决方案的时间复杂度是O(N)，并且由于我们将预先计算的最大值保存在内存中，所以我们的内存复杂度也是O(N)。

请注意，新解决方案的速度有多快；现在计算100,000个数据点的价格曲线只需不到十分之一秒，这意味着我们已经达成了一个有效且可接受的解决方案。

为了解决我们的问题，我们最初创建了一个非常简单的解决方案，但非常慢，稍微深入一点思考，我们可以将其性能提高到更快，然后我们发现了一个技巧，使我们能够为我们的问题提出一个有效的算法；同样的过程也适用于大多数需要特殊算法的问题。