tem*_*def 279
我喜欢这个问题.这是一个经典的面试问题,根据你的想法,你最终会得到更好,更好的解决方案.当然可以比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)解决方案!
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:
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):
If we use this approach, our recurrence relation is now
T(1) <= O(1)
T(n) <= 2T(n / 2) + O(1)
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!
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)st元素.那么这个值可以创建一个比我们对前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表示法中隐藏的常量因子进行一些优化,但除此之外我们不能指望找到任何更好的选项.
总的来说,这意味着我们有以下算法:
希望这可以帮助!
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. Here's the code:
# 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 code 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 pseudocode.
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
MSN*_*MSN 32
这是具有一点间接性的最大和子序列问题.最大和子序列问题给出一个整数列表,它可以是正数或负数,找到该列表的连续子集的最大总和.
您可以通过在连续几天之间获得利润或亏损来轻松地将此问题转换为该问题.因此,您可以将股票价格列表转换为例如[5, 6, 7, 4, 2]收益/损失列表[1, 1, -3, -2].然后,子序列和问题很容易解决:找到数组中元素总和最大的子序列
Aka*_*oon 15
我不确定为什么这被认为是一个动态的编程问题.我在课本和算法指南中使用O(n log n)运行时和空间O(log n)(例如编程访谈元素)看到了这个问题.这似乎是一个比人们正在做的更简单的问题.
这是通过跟踪最大利润,最低购买价格以及最终买入/卖出价格来实现的.当它遍历数组中的每个元素时,它会检查给定元素是否小于最低购买价格.如果是,则将最小购买价格指数(min)更新为该元素的索引.此外,对于每个元素,becomeABillionaire算法检查arr[i] - arr[min](当前元素和最小购买价格之间的差异)是否大于当前利润.如果是,则将利润更新为该差异,并将买入设置为arr[min]并将卖出设置为arr[i].
一次运行.
static void becomeABillionaire(int arr[]) {
int i = 0, buy = 0, sell = 0, min = 0, profit = 0;
for (i = 0; i < arr.length; i++) {
if (arr[i] < arr[min])
min = i;
else if (arr[i] - arr[min] > profit) {
buy = min;
sell = i;
profit = arr[i] - arr[min];
}
}
System.out.println("We will buy at : " + arr[buy] + " sell at " + arr[sell] +
" and become billionaires worth " + profit );
}
合着者:https://stackoverflow.com/users/599402/ephraim