最大单笔销售利润

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

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

1. 正确的买/卖对完全出现在上半年之内。
2. 正确的买/卖对完全在下半年发生。
3. 正确的买/卖对出现在两个半部分中-我们在上半年购买，然后在下半年出售。

我们可以通过在前一半和后一半递归调用我们的算法来获得（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. 买卖时间最大化利润。
2. 范围内的最小值。
3. 范围内的最大值。

最后两个值可以使用直接递归来递归计算，我们可以与要计算的递归同时运行（1）：

1. 单元素范围的最大值和最小值就是该元素。
2. 通过将输入分成两半，找到每个半的最大值和最小值，然后取各自的最大值和最小值，可以找到多个元素范围的最大值和最小值。

如果我们使用这种方法，那么我们的递归关系就是

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         7min         5         5        4          4         4    best      (5,5)     (5,10)   (5,10)     (5,10)    (5,10)

答：（5，10）

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

答案：（4、12）

 1       2       3      4      5min         1       1       1      1      1best      (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）空间。

希望这可以帮助！

编辑 ：如果您有兴趣，我已经
为这四种算法
编写了 Python版本， 以便您可以试用它们并判断它们的相对性能。这是代码：

# Four different algorithms for solving the maximum single-sell profit problem,# each of which have different time and space complexity.  This is one of my# all-time favorite algorithms questions, since there are so many different# answers that you can arrive at by thinking about the problem in slightly# different ways.## The maximum single-sell profit problem is defined as follows.  You are given# an array of stock prices representing the value of some stock over time.# Assuming that you are allowed to buy the stock exactly once and sell the# stock exactly once, what is the maximum profit you can make?  For example,# given the prices##  2, 7, 1, 8, 2, 8, 4, 5, 9, 0, 4, 5## The maximum profit you can make is 8, by buying when the stock price is 1 and# selling when the stock price is 9.  Note that while the greatest difference# in the array is 9 (by subtracting 9 - 0), we cannot actually make a profit of# 9 here because the stock price of 0 comes after the stock price of 9 (though# if we wanted to lose a lot of money, buying high and selling low would be a# great idea!)## In the event that there's no profit to be made at all, we can always buy and# sell on the same date.  For example, given these prices (which might# represent a buggy-whip manufacturer:)##      9, 8, 7, 6, 5, 4, 3, 2, 1, 0## The best profit we can make is 0 by buying and selling on the same day.## Let's begin by writing the simplest and easiest algorithm we know of that# can solve this problem - brute force.  We will just consider all O(n^2) pairs# of values, and then pick the one with the highest net profit.  There are# exactly n + (n - 1) + (n - 2) + ... + 1 = n(n + 1)/2 different pairs to pick# from, so this algorithm will grow quadratically in the worst-case.  However,# it uses only O(1) memory, which is a somewhat attractive feature.  Plus, if# our first intuition for the problem gives a quadratic solution, we can be# satisfied that if we don't come up with anything else, we can always have a# polynomial-time solution.def BruteForceSingleSellProfit(arr):    # Store the best possible profit we can make; initially this is 0.    bestProfit = 0;    # Iterate across all pairs and find the best out of all of them.  As a    # minor optimization, we don't consider any pair consisting of a single    # element twice, since we already know that we get profit 0 from this.    for i in range(0, len(arr)):        for j in range (i + 1, len(arr)): bestProfit = max(bestProfit, arr[j] - arr[i])    return bestProfit# This solution is extremely inelegant, and it seems like there just *has* to# be a better solution.  In fact, there are many better solutions, and we'll# see three of them.## The first insight comes if we try to solve this problem by using a divide-# and-conquer strategy.  Let's consider what happens if we split the array into# two (roughly equal) halves.  If we do so, then there are three possible# options about where the best buy and sell times are:## 1. We should buy and sell purely in the left half of the array.# 2. We should buy and sell purely in the right half of the array.# 3. We should buy in the left half of the array and sell in the right half of#    the array.## (Note that we don't need to consider selling in the left half of the array# and buying in the right half of the array, since the buy time must always# come before the sell time)## If we want to solve this problem recursively, then we can get values for (1)# and (2) by recursively invoking the algorithm on the left and right# subarrays.  But what about (3)?  Well, if we want to maximize our profit, we# should be buying at the lowest possible cost in the left half of the array# and selling at the highest possible cost in the right half of the array.# This gives a very elegant algorithm for solving this problem:##    If the array has size 0 or size 1, the maximum profit is 0.#    Otherwise:#       Split the array in half.#       Compute the maximum single-sell profit in the left array, call it L.#       Compute the maximum single-sell profit in the right array, call it R.#       Find the minimum of the first half of the array, call it Min#       Find the maximum of the second half of the array, call it Max#       Return the maximum of L, R, and Max - Min.## Let's consider the time and space complexity of this algorithm.  Our base# case takes O(1) time, and in our recursive step we make two recursive calls,# one on each half of the array, and then does O(n) work to scan the array# elements to find the minimum and maximum values.  This gives the recurrence##    T(1)     = O(1)#    T(n / 2) = 2T(n / 2) + O(n)## Using the Master Theorem, this recurrence solves to O(n log n), which is# asymptotically faster than our original approach!  However, we do pay a# (slight) cost in memory usage.  Because we need to maintain space for all of# the stack frames we use.  Since on each recursive call we cut the array size# in half, the maximum number of recursive calls we can make is O(log n), so# this algorithm uses O(n log n) time and O(log n) memory.def DivideAndConquerSingleSellProfit(arr):    # base case: If the array has zero or one elements in it, the maximum    # profit is 0.    if len(arr) <= 1:        return 0;    # Cut the array into two roughly equal pieces.    left  = arr[ : len(arr) / 2]    right = arr[len(arr) / 2 : ]    # Find the values for buying and selling purely in the left or purely in    # the right.    leftBest  = DivideAndConquerSingleSellProfit(left)    rightBest = DivideAndConquerSingleSellProfit(right)    # Compute the best profit for buying in the left and selling in the right.    crossBest = max(right) - min(left)    # Return the best of the three    return max(leftBest, rightBest, crossBest)# While the above algorithm for computing the maximum single-sell profit is# better timewise than what we started with (O(n log n) versus O(n^2)), we can# still improve the time performance.  In particular, recall our recurrence# relation:##    T(1) = O(1)#    T(n) = 2T(n / 2) + O(n)## Here, the O(n) term in the T(n) case comes from the work being done to find# the maximum and minimum values in the right and left halves of the array,# respectively.  If we could find these values faster than what we're doing# right now, we could potentially decrease the function's runtime.## The key observation here is that we can compute the minimum and maximum# values of an array using a divide-and-conquer approach.  Specifically:##    If the array has just one element, it is the minimum and maximum value.#    Otherwise:#       Split the array in half.#       Find the minimum and maximum values from the left and right halves.#       Return the minimum and maximum of these two values.## Notice that our base case does only O(1) work, and our recursive case manages# to do only O(1) work in addition to the recursive calls.  This gives us the# recurrence relation##    T(1) = O(1)#    T(n) = 2T(n / 2) + O(1)## Using the Master Theorem, this solves to O(n).## How can we make use of this result?  Well, in our current divide-and-conquer# solution, we split the array in half anyway to find the maximum profit we# could make in the left and right subarrays.  Could we have those recursive# calls also hand back the maximum and minimum values of the respective arrays?# If so, we could rewrite our solution as follows:##    If the array has size 1, the maximum profit is zero and the maximum and#       minimum values are the single array element.#    Otherwise:#       Split the array in half.#       Compute the maximum single-sell profit in the left array, call it L.#       Compute the maximum single-sell profit in the right array, call it R.#       Let Min be the minimum value in the left array, which we got from our#first recursive call.#       Let Max be the maximum value in the right array, which we got from our#second recursive call.#       Return the maximum of L, R, and Max - Min for the maximum single-sell#profit, and the appropriate maximum and minimum values found from#the recursive calls.## The correctness proof for this algorithm works just as it did before, but now# we never actually do a scan of the array at each step.  In fact, we do only# O(1) work at each level.  This gives a new recurrence##     T(1) = O(1)#     T(n) = 2T(n / 2) + O(1)## Which solves to O(n).  We're now using O(n) time and O(log n) memory, which# is asymptotically faster than before!## The pre for this is given below:def OptimizedDivideAndConquerSingleSellProfit(arr):    # If the array is empty, the maximum profit is zero.    if len(arr) == 0:        return 0    # This recursive helper function implements the above recurrence.  It    # returns a triple of (max profit, min array value, max array value).  For    # efficiency reasons, we always reuse the array and specify the bounds as    # [lhs, rhs]    def Recursion(arr, lhs, rhs):        # If the array has just one element, we return that the profit is zero        # but the minimum and maximum values are just that array value.        if lhs == rhs: return (0, arr[lhs], arr[rhs])        # Recursively compute the values for the first and latter half of the        # array.  To do this, we need to split the array in half.  The line        # below accomplishes this in a way that, if ported to other languages,        # cannot result in an integer overflow.        mid = lhs + (rhs - lhs) / 2        # Perform the recursion.        ( leftProfit,  leftMin,  leftMax) = Recursion(arr, lhs, mid)        (rightProfit, rightMin, rightMax) = Recursion(arr, mid + 1, rhs)        # Our result is the maximum possible profit, the minimum of the two        # minima we've found (since the minimum of these two values gives the        # minimum of the overall array), and the maximum of the two maxima.        maxProfit = max(leftProfit, rightProfit, rightMax - leftMin)        return (maxProfit, min(leftMin, rightMin), max(leftMax, rightMax))    # Using our recursive helper function, compute the resulting value.    profit, _, _ = Recursion(arr, 0, len(arr) - 1)    return profit# At this point we've traded our O(n^2)-time, O(1)-space solution for an O(n)-# time, O(log n) space solution.  But can we do better than this?## To find a better algorithm, we'll need to switch our line of reasoning.# Rather than using divide-and-conquer, let's see what happens if we use# dynamic programming.  In particular, let's think about the following problem.# If we knew the maximum single-sell profit that we could get in just the first# k array elements, could we use this information to determine what the# maximum single-sell profit would be in the first k + 1 array elements?  If we# could do this, we could use the following algorithm:##   Find the maximum single-sell profit to be made in the first 1 elements.#   For i = 2 to n:#      Compute the maximum single-sell profit using the first i elements.## How might we do this?  One intuition is as follows.  Suppose that we know the# maximum single-sell profit of the first k elements.  If we look at k + 1# elements, then either the maximum profit we could make by buying and selling# within the first k elements (in which case nothing changes), or we're# supposed to sell at the (k + 1)st price.  If we wanted to sell at this price# for a maximum profit, then we would want to do so by buying at the lowest of# the first k + 1 prices, then selling at the (k + 1)st price.## To accomplish this, suppose that we keep track of the minimum value in the# first k elements, along with the maximum profit we could make in the first# k elements.  Upon seeing the (k + 1)st element, we update what the current# minimum value is, then update what the maximum profit we can make is by# seeing whether the difference between the (k + 1)st element and the new# minimum value is.  Note that it doesn't matter what order we do this in; if# the (k + 1)st element is the smallest element so far, there's no possible way# that we could increase our profit by selling at that point.## To finish up this algorithm, we should note that given just the first price,# the maximum possible profit is 0.## This gives the following simple and elegant algorithm for the maximum single-# sell profit problem:##   Let profit = 0.#   Let min = arr[0]#   For k = 1 to length(arr):#       If arr[k] < min, set min = arr[k]#       If profit < arr[k] - min, set profit = arr[k] - min## This is short, sweet, and uses only O(n) time and O(1) memory.  The beauty of# this solution is that we are quite naturally led there by thinking about how# to update our answer to the problem in response to seeing some new element.# In fact, we could consider implementing this algorithm as a streaming# algorithm, where at each point in time we maintain the maximum possible# profit and then update our answer every time new data becomes available.## The final version of this algorithm is shown here:def DynamicProgrammingSingleSellProfit(arr):    # If the array is empty, we cannot make a profit.    if len(arr) == 0:        return 0    # Otherwise, keep track of the best possible profit and the lowest value    # seen so far.    profit = 0    cheapest = arr[0]    # Iterate across the array, updating our answer as we go according to the    # above pseudopre.    for i in range(1, len(arr)):        # Update the minimum value to be the lower of the existing minimum and        # the new minimum.        cheapest = min(cheapest, arr[i])        # Update the maximum profit to be the larger of the old profit and the        # profit made by buying at the lowest value and selling at the current        # price.        profit = max(profit, arr[i] - cheapest)    return profit# To summarize our algorithms, we have seen## Naive:  O(n ^ 2)   time, O(1)     space# Divide-and-conquer:O(n log n) time, O(log n) space# Optimized divide-and-conquer: O(n)       time, O(log n) space# Dynamic programming:          O(n)       time, O(1)     space