最大单笔销售利润

我喜欢这个问题。这是一个经典的面试问题，根据您的想法，您将最终获得越来越好的解决方案。当然，这样做可能比O（n 2）时间更好，而且我列出了三种您可以在此处考虑问题的方式。希望这能回答您的问题！

首先是分而治之的解决方案。让我们看看是否可以通过将输入分成两半，解决每个子数组中的问题，然后将两者组合在一起来解决此问题。事实证明，我们实际上可以做到这一点，并且可以做到高效！直觉如下。如果我们只有一天，那么最好的选择是在当天买入，然后在同一天将其卖回以赚取利润。否则，将阵列分成两半。如果我们考虑最佳答案可能是什么，它必须位于以下三个位置之一：

正确的买/卖对完全在上半年出现。 正确的买/卖对完全在下半年发生。 正确的买/卖对出现在两个半部分中-我们在上半年购买，然后在下半年出售。 我们可以通过在前一半和后一半递归调用我们的算法来获得（1）和（2）的值。对于选项（3），获得最高利润的方法是在上半年的最低点买入，在下半年的最高点卖出。通过对输入进行简单的线性扫描并找到两个值，我们可以找到两个一半的最小值和最大值。然后，这为我们提供了一种具有以下重复性的算法：

T(1) <= O(1) T(n) <= 2T(n / 2) + O(n) 使用主定理来解决递归问题，我们发现该过程以O（n lg n）的时间运行，并且将使用O（lg n）空间进行递归调用。我们刚刚击败了天真的O（n 2）解决方案！

可是等等！我们可以做得更好。请注意，重复出现O（n）项的唯一原因是我们必须扫描整个输入以尝试在每一半中找到最小值和最大值。由于我们已经在递归地探索每一部分，因此也许我们可以通过递归还递归存储在每一部分中的最小值和最大值来做得更好！换句话说，我们的递归递回三件事：

买卖时间最大化利润。 范围内的最小值。 范围内的最大值。 最后两个值可以使用直接递归来递归计算，我们可以与要计算的递归同时运行（1）：

单元素范围的最大值和最小值就是该元素。 通过将输入分为两半，找到每个半的最大值和最小值，然后取各自的最大值和最小值，可以找到多个元素范围的最大值和最小值。 如果我们使用这种方法，那么我们的递归关系就是

T(1) <= O(1) T(n) <= 2T(n / 2) + O(1) 在这里使用主定理可为我们提供O（n）和O（lg n）空间的运行时间，这甚至比我们原始的解决方案还要好！

但是请稍等-我们可以做得更好！让我们考虑使用动态编程解决此问题。想法是考虑以下问题。假设我们在看了前k个元素后就知道了问题的答案。我们能否利用我们对第（k + 1）个元素的了解并结合初始解决方案来解决第一个（k + 1）个元素的问题？如果是这样，我们可以通过求解第一个元素，然后是前两个，然后是前三个，依此类推，直到我们为前n个元素计算出问题，来得到一个很棒的算法。

让我们考虑如何做到这一点。如果我们只有一个要素，那么我们已经知道它必须是最佳的买卖对。现在假设我们知道前k个元素的最佳答案，并看一下第（k + 1）个元素。那么，此值可以创建比我们对前k个元素更好的解决方案的唯一方法是，如果前k个元素中的最小元素与该新元素之间的差异大于我们到目前为止计算出的最大差异。因此，假设在遍历元素时，我们跟踪两个值-到目前为止所看到的最小值，仅前k个元素便可以获取的最大利润。最初，到目前为止，我们看到的最小值是第一个元素，最大利润是零。当我们看到一个新元素时，我们首先通过计算以目前为止看到的最低价格购买并以当前价格出售来赚取多少来更新我们的最佳利润。如果这比我们到目前为止计算的最优值更好，那么我们将最优解更新为该新利润。接下来，我们将到目前为止看到的最小元素更新为当前最小元素和新元素的最小值。

由于在每个步骤中我们仅执行O（1）工作，并且我们仅要访问n个元素中的每个元素一次，因此这需要O（n）的时间才能完成！而且，它仅使用O（1）辅助存储。这和我们到目前为止所取得的一样好！

例如，在您的输入中，此算法可能会运行。数组的每个值之间的数字与该点算法所保存的值相对应。您实际上并不会存储所有这些内容（这会占用O（n）内存！），但是查看算法的发展会有所帮助：

        5        10        4          6         7

min 5 5 4 4 4
best (5,5) (5,10) (5,10) (5,10) (5,10) 答：（5，10）

        5        10        4          6        12

min 5 5 4 4 4
best (5,5) (5,10) (5,10) (5,10) (4,12) 答案：（4、12）

        1       2       3      4      5

min 1 1 1 1 1 best (1,1) (1,2) (1,3) (1,4) (1,5) 答案：（1、5）

我们现在可以做得更好吗？不幸的是，这并不是渐进的。如果使用的时间少于O（n），则无法查看大型输入上的所有数字，因此无法保证不会错过最佳答案（我们可以将其“隐藏”在我们的元素中）没看）。另外，我们不能使用少于O（1）的空间。可能会对big-O表示法中隐藏的常量因子进行了一些优化，但否则我们无法期望找到任何根本上更好的选择。

总体而言，这意味着我们具有以下算法：

天真：O（n 2）时间，O（1）空间。 分而治之：O（n lg n）时间，O（lg n）空间。 优化的分治法：O（n）时间，O（lg n）空间。 动态编程：O（n）时间，O（1）空间。 希望这可以帮助！