假设我们有一个包含n个整数的数组，表示单日股票价格。 我们想要找到一对（买入日，卖出日），其中 buyDay ≤ sellDay，并且如果我们在buyDay购买股票并在sellDay卖出，我们将最大化我们的利润。
显然，通过尝试所有可能的(buyDay，sellDay)对并从中选择最好的，可以得到O(n^2)时间复杂度的算法解决方案。 但是，是否存在更好的算法，例如运行时间为O（n）？
最大单笔销售利润
131
- Ajeet Ganga
7
2这是具有间接层级的最大子序列和问题。 - MSN
2@MSN：怎么回事？他根本没有看总和，而是在关注元素之间的差异。 - PengOne
2@PengOne，就像我说的那样，它有一级间接性。具体来说，您想要最大化连续几天的收益/损失总和。因此，将列表转换为收益/损失，并找到最大子序列和。 - MSN
为什么你不能找到最小值和最大值然后返回它们呢？我对这个问题有什么误解吗？ - PDN
1@PDN：那不行，因为最小值可以出现在最大值之前。你不能卖出股票（在这种情况下），然后再买回来。 - Ajeet Ganga
显示剩余2条评论
20个回答
307
我喜欢这个问题。它是一个经典的面试问题，根据你的思考方式，你会得到越来越好的解决方案。肯定可以在O(n2)时间内做到更好，我在这里列出了三种不同的思考该问题的方法。
首先是分治解法。让我们看看是否可以通过将输入分成两半，分别在每个子数组中解决问题，然后将它们组合起来来解决这个问题。事实证明我们确实可以这样做，并且可以高效地完成！其直觉如下所示：如果我们只有一天，最好的选择是在当天买入，然后在同一天卖出以获得无利润。否则，将数组分成两半。如果考虑最优答案可能在哪里，那么它必须在以下三个位置之一：
- 正确的买入/卖出对在第一个半部分完全发生。
- 正确的买入/卖出对在第二个半部分完全发生。
- 正确的买入/卖出对跨越两个半部分——我们在第一个半部分买入，然后在第二个半部分卖出。
我们可以通过递归调用算法来获得(1)和(2)的值。对于选项(3)，获得最高利润的方法是在第一个半部分的最低点买入，在第二个半部分的最大点卖出。我们可以通过对输入执行简单的线性扫描并找到这两个值来找到两半部分的最小值和最大值。然后，这就给出了以下算法递归：
T(1) <= O(1)
T(n) <= 2T(n / 2) + O(n)
使用 主定理 解决递归问题，我们发现该算法的时间复杂度为 O(n lg n)，并且递归调用需要 O(lg n) 的空间。我们已经击败了朴素的 O(n²) 解法！
但是等等！我们可以做得比这更好。注意到我们递归中唯一的 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 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)的空间。在大O符号中可能隐藏着某些常数因子的优化，但除此之外，我们不能指望找到任何根本上更好的选择。
总的来说，这意味着我们有以下算法：
- Naive：O(n2)时间，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) = 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
- templatetypedef
10
1@FrankQ.- 递归调用需要空间，但通常这些调用是依次执行的。这意味着编译器可以在调用之间重复使用内存；一旦一个调用返回，下一个调用就可以重用它的空间。因此，您只需要内存来保存一个函数调用，因此内存使用量与调用堆栈的最大深度成比例。由于递归在O(log n)级别终止，因此只需要使用O(log n)内存。这样清楚了吗？ - templatetypedef
动态规划的概念并不是解释O(n)时间复杂度解决方案所必需的，但将所有这些类型的算法联系起来是很好的。 - Rn222
@templatetypedef 如果我们从M美元的预算开始，而不是单一股票，而是有m只股票在n天内以给定价格，我们将如何改变动态规划方法呢？
也就是说，我们将购买的股票单位数量和可用的股票数据从1只股票变化到n只股票（就像之前我们只有谷歌，现在我们还有其他5家公司的股票数据）。 - Ronak Agrawal
@Natxet 这是真的。我想，有了这里提供的直觉，更新代码以返回起始和结束日期不应该花费太长时间。 我认为这是一个合理的“读者练习”。 :-) - templatetypedef
你能帮我解决DivideAndConquerSingleSellProfit算法中如何找出最佳买入和卖出日的问题吗？ - Hacker
显示剩余5条评论
32
这是一个略带巧妙的最大子序和问题。最大子序和问题给定一个由正数或负数组成的整数列表，找到那个列表中连续子集的最大总和。
你可以通过计算相邻天数之间的利润或损失来将此问题轻松转换为该问题。因此，你需要将股票价格列表转换成收益/亏损列表，例如：[5, 6, 7, 4, 2] 转换成 [1, 1, -3, -2]。然后最大子序列和问题就很容易解决了：在数组中查找具有最大元素和的子序列
- MSN
3
1我认为事情并不完全是这样的，因为如果你在某个初始日购买股票，你就无法获得前一天的增量收益。这种方法中不存在这个问题吗？ - templatetypedef
1@templatetypedef，这就是为什么您要跟踪最大总和和当前序列总和。当当前序列总和低于零时，您知道您将无法从该序列中赚到任何钱，因此您可以重新开始。通过跟踪最大总和，您将自动找到最佳的购买/销售日期。 - MSN
6顺便提一下，你的回答中也是这样做的。 - MSN
17
我不确定为什么这被认为是一道动态规划问题。我在教科书和算法指南中看到这个问题使用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 );
}
- Akash Magoon
2
以下是我的Java解决方案：
public static void main(String[] args) {
int A[] = {5,10,4,6,12};
int min = A[0]; // Lets assume first element is minimum
int maxProfit = 0; // 0 profit, if we buy & sell on same day.
int profit = 0;
int minIndex = 0; // Index of buy date
int maxIndex = 0; // Index of sell date
//Run the loop from next element
for (int i = 1; i < A.length; i++) {
//Keep track of minimum buy price & index
if (A[i] < min) {
min = A[i];
minIndex = i;
}
profit = A[i] - min;
//If new profit is more than previous profit, keep it and update the max index
if (profit > maxProfit) {
maxProfit = profit;
maxIndex = i;
}
}
System.out.println("maxProfit is "+maxProfit);
System.out.println("minIndex is "+minIndex);
System.out.println("maxIndex is "+maxIndex);
}
- Rohit Mendiratta
3
@Nitiraj，是的，这个解决方案是正确的，但我想请您阅读templatetypedef提供的答案，因为在templatetypedef提供的答案中，包括了所有可能的解决方案，包括Rohit发布的那个。Rohit的解决方案实际上是templatetypedef提供的最后一个使用动态规划的O(n)解决方案的实现。 - nits.kk
1假设你的数组是int A[] = {5, 4, 6 ,7 ,6 ,3 ,2, 5}; 根据你的逻辑，你会在索引6买入，然后在索引3卖出。这是错误的。你不能在过去卖出。卖出的索引必须大于购买的索引。 - developer747
1上面的代码解决方案“几乎”正确。但是它打印的是绝对最小索引，而不是“买入”价格的索引。要更正，您需要另一个变量，比如minBuyIndex，在“if（profit> maxProfit）”块中进行更新并打印该变量。 - javabrew
2
问题与最大子序列相同。我用动态规划解决了这个问题。跟踪当前和之前的（利润，购买日期和销售日期）。如果当前高于之前，则用当前替换之前。
int prices[] = { 38, 37, 35, 31, 20, 24, 35, 21, 24, 21, 23, 20, 23, 25, 27 };
int buyDate = 0, tempbuyDate = 0;
int sellDate = 0, tempsellDate = 0;
int profit = 0, tempProfit =0;
int i ,x = prices.length;
int previousDayPrice = prices[0], currentDayprice=0;
for(i=1 ; i<x; i++ ) {
currentDayprice = prices[i];
if(currentDayprice > previousDayPrice ) { // price went up
tempProfit = tempProfit + currentDayprice - previousDayPrice;
tempsellDate = i;
}
else { // price went down
if(tempProfit>profit) { // check if the current Profit is higher than previous profit....
profit = tempProfit;
sellDate = tempsellDate;
buyDate = tempbuyDate;
}
// re-intialized buy&sell date, profit....
tempsellDate = i;
tempbuyDate = i;
tempProfit =0;
}
previousDayPrice = currentDayprice;
}
// if the profit is highest till the last date....
if(tempProfit>profit) {
System.out.println("buydate " + tempbuyDate + " selldate " + tempsellDate + " profit " + tempProfit );
}
else {
System.out.println("buydate " + buyDate + " selldate " + sellDate + " profit " + profit );
}
- Vikas
1
最高票答案没有考虑最大利润为负的情况，需要进行修改以允许这种情况。可以通过将循环范围限制为(len(a)-1)并改变利润确定的方式来实现这一点，即将索引向后移动一个位置。
def singSellProfit(a):
profit = -max(a)
low = a[0]
for i in range(len(a) - 1):
low = min(low, a[i])
profit = max(profit, a[i + 1] - low)
return profit
将此函数版本与先前的数组版本进行比较：
s = [19,11,10,8,5,2]
singSellProfit(s)
-1
DynamicProgrammingSingleSellProfit(s)
0
- Danny Bubb
1
最大单次卖出利润，O(n)解法。
这是一个关于在100k个整数的随机数据集上进行时间复杂度测试的项目，比较了O(N)和O(n^2)方法。 O(n^2)需要2秒，而O(n)只需要0.01秒。
这是一种较慢的O(n^2)方法，它会为每一天循环遍历其余的天数，即双重循环。
function stocks_n(price_list){
var maxDif=0, min=price_list[0]
for (var i in price_list){
p = price_list[i];
if (p<min)
min=p
else if (p-min>maxDif)
maxDif=p-min;
}
return maxDif
}
这是一个关于在100k个整数的随机数据集上进行时间复杂度测试的项目，比较了O(N)和O(n^2)方法。 O(n^2)需要2秒，而O(n)只需要0.01秒。
https://github.com/gulakov/complexity.js
function stocks_n2(ps){
for (maxDif=0,i=_i=0;p=ps[i++];i=_i++)
for (;p2=ps[i++];)
if (p2-p>maxDif)
maxDif=p2-p
return maxDif
}
这是一种较慢的O(n^2)方法，它会为每一天循环遍历其余的天数，即双重循环。
- Alex Gulakov
1
这是一个有趣的问题，因为它看起来很难，但仔细思考可以得出一种简洁优雅的解决方案。
正如已经指出的那样，它可以通过O(N^2)的暴力方法解决。对于数组（或列表）中的每个条目，迭代所有先前的条目以获得最小值或最大值，具体取决于问题是寻找最大收益还是最大损失。
以下是如何考虑O(N)解决方案：每个条目都代表一个新的可能最大值（或最小值）。然后，我们只需要保存之前的最小值（或最大值），并将差异与当前和之前的最小值（或最大值）进行比较。非常简单。
以下是Java作为JUnit测试的代码：
import org.junit.Test;
public class MaxDiffOverSeriesProblem {
@Test
public void test1() {
int[] testArr = new int[]{100, 80, 70, 65, 95, 120, 150, 75, 95, 100, 110, 120, 90, 80, 85, 90};
System.out.println("maxLoss: " + calculateMaxLossOverSeries(testArr) + ", maxGain: " + calculateMaxGainOverSeries(testArr));
}
private int calculateMaxLossOverSeries(int[] arr) {
int maxLoss = 0;
int idxMax = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] > arr[idxMax]) {
idxMax = i;
}
if (arr[idxMax] - arr[i] > maxLoss) {
maxLoss = arr[idxMax] - arr[i];
}
}
return maxLoss;
}
private int calculateMaxGainOverSeries(int[] arr) {
int maxGain = 0;
int idxMin = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] < arr[idxMin]) {
idxMin = i;
}
if (arr[i] - arr[idxMin] > maxGain) {
maxGain = arr[i] - arr[idxMin];
}
}
return maxGain;
}
}
在计算最大亏损时，我们会追踪到当前条目之前的列表中的最大值（购买价格）。然后，我们计算最大值与当前条目之间的差异。如果max - current > maxLoss，则将此差异作为新的maxLoss。由于max的索引保证小于current的索引，我们保证'buy'日期早于'sell'日期。
在计算最大收益时，一切都反过来了。我们追踪到当前条目之前的列表中的最小值。我们计算最小值与当前条目之间的差异（通过颠倒减法顺序）。如果current - min > maxGain，则将此差异作为新的maxGain。同样，'buy'（min）的索引在current（'sell'）的索引之前。
我们只需要追踪maxGain（或maxLoss）和min或max的索引，但不需要两者都追踪，也不需要比较索引以验证'buy'是否小于'sell'，因为这是自然得到的。
- Steven Solomon
1
public static double maxProfit(double [] stockPrices)
{
double initIndex = 0, finalIndex = 0;
double tempProfit = list[1] - list[0];
double maxSum = tempProfit;
double maxEndPoint = tempProfit;
for(int i = 1 ;i<list.length;i++)
{
tempProfit = list[ i ] - list[i - 1];;
if(maxEndPoint < 0)
{
maxEndPoint = tempProfit;
initIndex = i;
}
else
{
maxEndPoint += tempProfit;
}
if(maxSum <= maxEndPoint)
{
maxSum = maxEndPoint ;
finalIndex = i;
}
}
System.out.println(initIndex + " " + finalIndex);
return maxSum;
}
这是我的解决方案。修改了最大子序列算法。以O(n)的时间复杂度解决了问题。我认为无法更快地完成。
- Afaque
1
我想到了一个简单的解决方案——代码更具自说明性。这是一道动态规划问题。
代码没有考虑错误检查和边缘情况。它只是一个示例，旨在给出解决问题的基本逻辑思路。
代码没有考虑错误检查和边缘情况。它只是一个示例，旨在给出解决问题的基本逻辑思路。
namespace MaxProfitForSharePrice
{
class MaxProfitForSharePrice
{
private static int findMax(int a, int b)
{
return a > b ? a : b;
}
private static void GetMaxProfit(int[] sharePrices)
{
int minSharePrice = sharePrices[0], maxSharePrice = 0, MaxProft = 0;
int shareBuyValue = sharePrices[0], shareSellValue = sharePrices[0];
for (int i = 0; i < sharePrices.Length; i++)
{
if (sharePrices[i] < minSharePrice )
{
minSharePrice = sharePrices[i];
// if we update the min value of share, we need to reset the Max value as
// we can only do this transaction in-sequence. We need to buy first and then only we can sell.
maxSharePrice = 0;
}
else
{
maxSharePrice = sharePrices[i];
}
// We are checking if max and min share value of stock are going to
// give us better profit compare to the previously stored one, then store those share values.
if (MaxProft < (maxSharePrice - minSharePrice))
{
shareBuyValue = minSharePrice;
shareSellValue = maxSharePrice;
}
MaxProft = findMax(MaxProft, maxSharePrice - minSharePrice);
}
Console.WriteLine("Buy stock at ${0} and sell at ${1}, maximum profit can be earned ${2}.", shareBuyValue, shareSellValue, MaxProft);
}
static void Main(string[] args)
{
int[] sampleArray = new int[] { 1, 3, 4, 1, 1, 2, 11 };
GetMaxProfit(sampleArray);
Console.ReadLine();
}
}
}
- vran freelancer
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接