最大的单一销售利润 [英] Maximum single-sell profit

问题描述

假设我们给出n个整数数组重新presenting股价单日。我们希望找到一个对（buyDay，sellDay），与buyDay与乐; sellDay，这样，如果我们买的股票上buyDay和sellDay把它卖了，我们会最大限度地提高我们的利润。

Suppose we are given an array of n integers representing stock prices on a single day. We want to find a pair (buyDay, sellDay), with buyDay ≤ sellDay, such that if we bought the stock on buyDay and sold it on sellDay, we would maximize our profit.

显然，复杂度为O（N ² ）解决方案的算法，尝试了所有可能的（buyDay，sellDay）对，并采取最好的所有他们的。但是，有没有更好的算法，或许是一个运行在O（n）的时间？

Clearly there is an O(n²) solution to the algorithm by trying out all possible (buyDay, sellDay) pairs and taking the best out of all of them. However, is there a better algorithm, perhaps one that runs in O(n) time?

推荐答案

我喜欢这个问题。这是一个典型的面试问题，并根据您如何看待它，你最终会越来越好，更好的解决方案。这当然可以做到这一点为O更好的（N ² ）的时间，我列出了三种不同的方式，你可以考虑一下这里的问题。希望这回答您的问题！

I love this problem. It's a classic interview question and depending on how you think about it, you'll end up getting better and better solutions. It's certainly possible to do this in better than O(n²) time, and I've listed three different ways that you can think about the problem here. Hopefully this answers your question!

一，分而治之的解决方案。让我们来看看，如果我们可以通过把输入的一半，在每个子阵列解决问题，那么两者结合起来解决这个问题。事实证明，我们确实可以做到这一点，并能如此有效呢！直觉如下。如果我们有一天，最好的选择是购买的那一天，然后在同一天没有利润返销。否则，分裂阵列分为两半。如果我们想想的最佳答案可能是，它必须在三个位置之一：

First, the divide-and-conquer solution. Let's see if we can solve this by splitting the input in half, solving the problem in each subarray, then combining the two together. Turns out we actually can do this, and can do so efficiently! The intuition is as follows. If we have a single day, the best option is to buy on that day and then sell it back on the same day for no profit. Otherwise, split the array into two halves. If we think about what the optimal answer might be, it must be in one of three places:

1. 在正确的买入/卖出一双完全发生在上半年之内。
2. 在正确的买入/卖出一双完全发生在下半年内。
3. 在正确的买/卖对发生在这两个半 - 我们买在上半场，然后卖掉下半年
。

我们可以得到的值（1）和（2）通过递归调用我们的算法在第一和第二半部。对于选项（3）的方式，使利润最高的是在最低点在今年上半年购买并在下半年销售的最大点。我们可以通过只是在做在输入一个简单的线性扫描和寻找这两个值找到最小和最大值中的两半。这就给了我们一个算法有以下复发：

We can get the values for (1) and (2) by recursively invoking our algorithm on the first and second halves. For option (3), the way to make the highest profit would be to buy at the lowest point in the first half and sell in the greatest point in the second half. We can find the minimum and maximum values in the two halves by just doing a simple linear scan over the input and finding the two values. This then gives us an algorithm with the following recurrence:

T(1) <= O(1)
T(n) <= 2T(n / 2) + O(n)

使用主定理的解决了复发，我们发现，这个运行在为O（n LG电子n）的时间，将使用O（LG n）的空间，递归调用。我们刚刚击败了天真的为O（n ² ）解决方案！

Using the Master Theorem to solve the recurrence, we find that this runs in O(n lg n) time and will use O(lg n) space for the recursive calls. We've just beaten the naive O(n²) solution!

别急！我们可以做得比这更好。请注意，我们有一个O（n）的任期在我们的再次发生的唯一原因是，我们不得不扫描整个输入试图找到的最小值和最大值的各占一半。既然我们已经递归探索各占一半，也许我们可以通过做具有更好的递归也交还存储在每个一半的最小值和最大值！换句话说，我们的递归手回三件事情：

But wait! We can do much better than this. Notice that the only reason we have an O(n) term in our recurrence is that we had to scan the entire input trying to find the minimum and maximum values in each half. Since we're already recursively exploring each half, perhaps we can do better by having the recursion also hand back the minimum and maximum values stored in each half! In other words, our recursion hands back three things:

1. 的买入和卖出的时间，以实现利润​​最大化。
2. 在整体的最小值范围内。
3. 在整体的最大值范围内。

这些最后两个值可以递归使用简单的递归，我们可以在同一时间运行的递归来计算被计算（1）：

These last two values can be computed recursively using a straightforward recursion that we can run at the same time as the recursion to compute (1):

1. 在一个单一的元素范围的最大值和最小值是正义的元素。
一个多单元的范围
2. 的最大值和最小值可以通过将所述输入在半，寻找各一半的最大值和最小值，然后取它们各自的最大和最小找到。

1. The max and min values of a single-element range are just that element.
2. The max and min values of a multiple element range can be found by splitting the input in half, finding the max and min values of each half, then taking their respective max and min.

如果我们使用这种方法，我们的递推关系现在是

If we use this approach, our recurrence relation is now

T(1) <= O(1)
T(n) <= 2T(n / 2) + O(1)

这里使用的主定理让我们为O（n）与O（LG n）的空间，它甚至比我们原来的解决方案，更好的运行时间！

Using the Master Theorem here gives us a runtime of O(n) with O(lg n) space, which is even better than our original solution!

但是且慢 - 我们可以做的比这更好！让我们想想用动态规划解决这个问题。这个想法将考虑如下问题。假设我们知道这个问题的答案在看前k元素之后。我们能不能​​用我们的第（k + 1）个单元的知识，再加上我们初步的解决方案，解决了第一个（K + 1）元素的问题？如果是这样，我们可以得到一个很大的算法将通过解决问题的第一要素，那么前两个，然后是前三个，等等，直到我们就计算它的第n个元素。

But wait a minute - we can do even better than this! Let's think about solving this problem using dynamic programming. The idea will be to think about the problem as follows. Suppose that we knew the answer to the problem after looking at the first k elements. Could we use our knowledge of the (k+1)st element, combined with our initial solution, to solve the problem for the first (k+1) elements? If so, we could get a great algorithm going by solving the problem for the first element, then the first two, then the first three, etc. until we'd computed it for the first n elements.

让我们来想想如何做到这一点。如果我们只有一个元素，我们已经知道，它是最好的买入/卖出一双。现在假设我们知道第k个元素的最佳答案，并期待在（K + 1）个元素。然后，这个值可以创建一个溶液比我们有用于第一k个元素更好的唯一途径是如果之间的最小的前k个元素，并且新元件的差大于到目前为止，我们已经计算出的最大区别。因此，假设是，当我们要去对面的元素，我们保持两个值的轨迹 - 我们已经看到，到目前为止的最低值，而最大的利润，我们可以让只用前k元素。最初，我们到目前为止看到的最小值是第一要素，最大利润为零。当我们看到一个新的元素，我们首先通过计算多少，我们会通过购买以最低的价格看出，到目前为止，销售在目前的价位做出更新我们的最佳利益。如果这是比我们到目前为止所计算的最优值好，那么我们更新了最佳的解决方案是这一新的利润。下一步，我们更新看到迄今最小元素是当前最小元素的最小和新的元素

Let's think about how to do this. If we have just one element, we already know that it has to be the best buy/sell pair. Now suppose we know the best answer for the first k elements and look at the (k+1)st element. Then the only way that this value can create a solution better than what we had for the first k elements is if the difference between the smallest of the first k elements and that new element is bigger than the biggest difference we've computed so far. So suppose that as we're going across the elements, we keep track of two values - the minimum value we've seen so far, and the maximum profit we could make with just the first k elements. Initially, the minimum value we've seen so far is the first element, and the maximum profit is zero. When we see a new element, we first update our optimal profit by computing how much we'd make by buying at the lowest price seen so far and selling at the current price. If this is better than the optimal value we've computed so far, then we update the optimal solution to be this new profit. Next, we update the minimum element seen so far to be the minimum of the current smallest element and the new element.

由于在每一步，我们都只有O（1）工作和每一个n个元素，我们正在访问恰好一次，这需要O（n）的时间来完成！此外，它仅使用O（1）辅助存储。这是一样好，到目前为止，我们已经得到了！

Since at each step we do only O(1) work and we're visiting each of the n elements exactly once, this takes O(n) time to complete! Moreover, it only uses O(1) auxiliary storage. This is as good as we've gotten so far!

作为一个例子，你的投入，这就是这个算法可能运行。每个阵列的值之间在-的数字对应于由该算法在该点内的值。你不会真地存储所有这些（这将需要O（n）的内存！），但它有助于了解该算法的演变：

As an example, on your inputs, here's how this algorithm might run. The numbers in-between each of the values of the array correspond to the values held by the algorithm at that point. You wouldn't actually store all of these (it would take O(n) memory!), but it's helpful to see the algorithm evolve:

        5        10         4         6        7
min         5         5        4          4         4    
best      (5,5)     (5,10)   (5,10)     (5,10)    (5,10)

答：（5,10）

Answer: (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）

Answer: (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）

Answer: (1, 5)

可我们现在做的更好？不幸的是，不是在渐近感。如果我们不是O（n）的时间少用，我们不能只看大投入所有的数字，因此不能保证我们不会错过最佳答案（我们可能只是隐藏它的元素，我们没看）。另外，我们不能使用比O（1）空间的任何减少。可能有一些优化，以大隐于O符号常量因素，但除此之外，我们不能指望找到任何从根本上更好的选择。

Can we do better now? Unfortunately, not in an asymptotic sense. If we use less than O(n) time, we can't look at all the numbers on large inputs and thus can't guarantee that we won't miss the optimal answer (we could just "hide" it in the elements we didn't look at). Plus, we can't use any less than O(1) space. There might be some optimizations to the constant factors hidden in the big-O notation, but otherwise we can't expect to find any radically better options.

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

Overall, this means that we have the following algorithms:

• 天真：为O（n ² ）时间，O（1）空间
• 分而治之：为O（n LG电子n）时间，O（LG n）的空间
• 优化分而治之：O（n）时间，O（LG n）的空间
• 动态规划：O（n）时间，O（1）空间

• Naive: O(n²) time, O(1) space.
• Divide-and-Conquer: O(n lg n) time, O(lg n) space.
• Optimized Divide-and-Conquer: O(n) time, O(lg n) space.
• Dynamic programming: O(n) time, O(1) space.

希望这有助于！

修改：如果您有兴趣，我有codeD起来的的一个Python版本，这四种算法 这样就可以玩弄他们，并判断它们的相对表现。尽情享受吧！

EDIT: If you're interested, I've coded up a Python version of these four algorithms so that you can play around with them and judge their relative performances. Enjoy!

这篇关于最大的单一销售利润的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！