最大单一销售利润

假设我们在一天内得到一个n个整数代表股票价格。 我们希望find一个（buyDay，sellDay） ， buyDay≤sellDay ，这样如果我们在buyDay买入股票并在卖出date卖出 ，我们将最大化我们的利润。

很明显，通过尝试所有可能的（buyDay，sellDay）对，并从所有这些对中最好地解决algorithm的O（n ² ）解决scheme。 然而，有没有更好的algorithm，也许是一个运行在O（n）时间？

Answer 1

我喜欢这个问题。 这是一个经典的面试问题，取决于你如何看待，最终你会得到更好，更好的解决scheme。 当然可以做得比O（n ² ）更好，我已经列出了三种不同的方式，你可以在这里考虑这个问题。 希望这回答你的问题！

首先是分而治之的解决scheme。 让我们看看是否可以通过将input分成两半来解决这个问题，在每个子arrays中解决问题，然后将两者结合在一起。 事实certificate，我们其实可以做到这一点，并可以有效地做到这一点！ 直觉如下。 如果我们有一天的时间，最好的select就是当天买入，然后在同一天卖出，无利可图。 否则，将数组分成两半。 如果我们考虑最佳答案可能是什么，它必须在三个地方之一：

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

我们可以通过在第一和第二部分recursion地调用我们的algorithm来获得（1）和（2）的值。 对于期权（3）来说，获得最高利润的方法是在上半年的最低点买入，在下半年卖出最高点。 通过对input进行简单的线性扫描并find两个值，我们可以在两半中find最小值和最大值。 然后这给了我们一个algorithm以下的重现：

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

使用主定理来解决复发问题，我们发现它运行在O（n lg n）时间，并将使用recursion调用的O（lg n）空间。 我们刚刚打败了天真的O（N ² ）解决scheme！

可是等等！ 我们可以做得比这更好。 请注意，我们在重现中有一个O（n）项的唯一原因是我们必须扫描整个input，试图在每一半中find最小值和最大值。 既然我们已经recursion地探索了每一半，也许我们可以做得更好，通过recursion递交存储在每一半的最小值和最大值！ 换句话说，我们的recursion回传三件事情：

1. 买卖时间最大化利润。
2. 整个范围内的最小值。
3. 整个范围内的最大值。

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

1. 单元素范围的最大值和最小值就是这个元素。
2. 多元素范围的最大值和最小值可以通过将input分成两半来find，找出每一半的最大值和最小值，然后取其各自的最大值和最小值。

如果我们使用这种方法，现在我们的复发关系

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

在这里使用主定理给我们提供了O（n）和O（lg n）空间的运行时间，这比我们原来的解决scheme还要好！

但等一下 – 我们可以做得比这更好！ 让我们考虑使用dynamic编程来解决这个问题。 这个想法将如下考虑这个问题。 假设我们在查看前k个元素之后就知道了问题的答案。 我们可以用（k + 1）st单元的知识，结合我们的初始解来解决第一个（k + 1）单元的问题吗？ 如果是这样的话，我们可以通过解决第一个元素的问题，然后是前两个，然后是前三个，直到我们为前n个元素计算出问题来得到一个好的algorithm。

我们来考虑如何做到这一点。 如果我们只有一个元素，我们已经知道它必须是最好的买/卖对。 现在假设我们知道前k个元素的最佳答案并且看第（k + 1）个元素。 那么这个值可以创造一个比我们对前k个元素更好的解决scheme的唯一途径就是如果最初的k个元素中的最小元素和这个新元素之间的差异大于我们目前计算的最大差异。 因此，假设我们正在穿越这些元素，我们会跟踪两个值 – 迄今为止我们已经看到的最小值，以及我们可以用最初的k个元素获得的最大利润。 最初，我们目前看到的最小值是第一个元素，最大的利润是零。 当我们看到一个新的元素时，我们首先通过计算我们通过以迄今为止看到的最低价格买入并以当前价格进行卖出来制造多less来更新我们的最佳利润。 如果这比我们迄今为止计算的最优值更好，那么我们更新最优解为新的利润。 接下来，我们将迄今为止所看到的最小元素更新为当前最小元素和新元素的最小值。

由于在每一步我们只做O（1）工作，而且我们正在访问每个n元素一次，这需要O（n）时间来完成！ 而且，它只使用O（1）辅助存储。 这和迄今为止一样好！

作为一个例子，在你的input上，这里是algorithm的运行方式。 数组中的每个值之间的数字对应于该algorithm在该点保持的值。 你不会真的存储所有这些（这将需要O（n）内存！），但看到algorithm演变是有帮助的：

  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）

我们现在可以做得更好吗？ 不幸的是，没有渐进的意义。 如果我们使用的时间less于O（n），那么我们就不能看大input上的所有数字，因此不能保证我们不会错过最佳答案（我们可以将它隐藏在元素中没看）。 另外，我们不能使用任何小于O（1）的空间。 大O符号中隐藏的常数因子可能会有一些优化，否则我们不能指望find更好的select。

总的来说，这意味着我们有以下algorithm：

• 天真：O（N ² ）时间，O（1）空间。
• 分而治之：O（n lg n）时间，O（lg n）空间。
• 优化分而治之：O（n）时间，O（lg n）空间。
• dynamic编程：O（n）时间，O（1）空间。

希望这可以帮助！

编辑 ：如果你有兴趣，我已经编码了这四种algorithm的Python版本，以便你可以玩弄他们，并判断他们的相对performance。 代码如下：

 # 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 

Answer 2

这是一个间接点的最大总和子序列问题。 最大总和子序列问题给出一个可能是正数或负数的整数列表，find该列表的一个连续子集的最大和。

通过在连续的几天之间获取利润或损失，您可以轻松地将此问题转换为该问题。 因此，您可以将股票价格列表（例如[5, 6, 7, 4, 2]转换为收益/损失列表，例如[1, 1, -3, -2] 。 这个子序列和问题很容易解决： 在一个数组中find元素和最大的子序列

Answer 3

我不确定为什么这被认为是一个dynamic编程问题。 我在教科书和algorithm指南中看到过使用O（n log n）运行时和O（log n）作为空间（例如编程访问元素）的问题。 这似乎是一个比人们想象的要简单得多的问题。

这是通过追踪最大利润，最低购买价格以及最优购买/销售价格来实现的。 当它通过数组中的每个元素时，它会检查给定元素是否小于最低购买价格。 如果是，则最小购买价格指数（ min ）被更新为该要素的指数。 此外，对于每个元素，成为becomeABillionairealgorithm检查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

Answer 4

这里是我的Java解决scheme：

 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); } 

Answer 5

问题与最大子序列相同
我使用dynamic编程来解决它。 跟踪当前和以前（利润，buydate和出售date）如果电stream比先前更高，然后用当前replace之前。

  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 ); } 

Answer 6

我想出了一个简单的解决scheme – 代码更多的是不言自明的。 这是那些dynamic编程问题之一。

代码不会负责错误检查和边缘情况。 它只是一个样本，给出了解决问题的基本逻辑的想法。

 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(); } } } 

Answer 7

 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; } 

这是我的解决scheme。 修改最大的子序列algorithm。 解决O（n）中的问题。 我认为这不能做得更快。

Answer 8

这是一个有趣的问题，因为它似乎很难，但仔细的思考会产生一个优雅的，简化的解决scheme。

如前所述，它可以在O（N ^ 2）时间内解决蛮力。 对于数组（或列表）中的每个条目，遍历所有以前的条目以获取最小或最大取决于问题是find最大的收益还是损失。

以下是如何考虑O（N）中的解决scheme：每个条目代表一个新的可能的最大值（或最小值）。 然后，我们所要做的就是保存先前的最小值（或最大值），然后比较差值与当前的最小值（或最大值）。 十分简单。

这是Java中的代码，作为JUnittesting：

 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。 由于最大指数保证小于当前指数，我们保证“买入”date小于“卖出”date。

在计算最大收益的情况下，一切都会颠倒过来。 我们跟踪列表中最小的分数。 我们计算min和当前条目之间的差异（在减法中颠倒顺序）。 如果current – min> maxGain，那么我们将这个diff保留为新的maxGain。 再次，“买入”指数（分）在当前指数（“卖出”）之前。

我们只需要跟踪maxGain（或maxLoss）和min或max的指数，但不是两者都是，我们不需要比较指数来validation“买入”小于“卖出”，因为我们自然得到这个。

Answer 9

最大单一销售利润，O（n）解决scheme

 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 } 

这里有一个项目，对10k随机数据集上的o（N）和o（n ^ 2）进行时间复杂度testing。 O（n ^ 2）需要2秒，而O（n）需要0.01秒

gulakov/complexity.html

 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）方法，通过每天的其余时间循环，双循环。

Answer 10

 static void findmaxprofit(int[] stockvalues){ int buy=0,sell=0,buyingpoint=0,sellingpoint=0,profit=0,currentprofit=0; int finalbuy=0,finalsell=0; if(stockvalues.length!=0){ buy=stockvalues[0]; } for(int i=1;i<stockvalues.length;i++){ if(stockvalues[i]<buy&&i!=stockvalues.length-1){ buy=stockvalues[i]; buyingpoint=i; } else if(stockvalues[i]>buy){ sell=stockvalues[i]; sellingpoint=i; } currentprofit=sell-buy; if(profit<currentprofit&&sellingpoint>buyingpoint){ finalbuy=buy; finalsell=sell; profit=currentprofit; } } if(profit>0) System.out.println("Buy shares at "+finalbuy+" INR and Sell Shares "+finalsell+" INR and Profit of "+profit+" INR"); else System.out.println("Don't do Share transacations today"); } 

Answer 11

A possibility to determine the maximum profit might be to keep track of the left-side minimum and right-side maximum elements in the array at each index in the array. When you are then iterating through the stock prices, for any given day you will know the lowest price up to that day, and you will also know the maximum price after (and including) that day.

For instance, let's define a min_arr and max_arr , with the given array being arr . Index i in min_arr would be the minimum element in arr for all indices <= i (left of and including i). Index i in max_arr would be the maximum element in arr for all indices >= i (right of and including i). Then, you could find the maximum difference between the corresponding elements in max_arr and `min_arr':

 def max_profit(arr) min_arr = [] min_el = arr.first arr.each do |el| if el < min_el min_el = el min_arr << min_el else min_arr << min_el end end max_arr = [] max_el = arr.last arr.reverse.each do |el| if el > max_el max_el = el max_arr.unshift(max_el) else max_arr.unshift(max_el) end end max_difference = max_arr.first - min_arr.first 1.upto(arr.length-1) do |i| max_difference = max_arr[i] - min_arr[i] if max_difference < max_arr[i] - min_arr[i] end return max_difference end 

This should run in O(n) time, but I believe it uses up a lot of space.

Answer 12

Here's my solution

public static int maxProfit(ArrayList in){

  int min = in.get(0), max = 0; for(int i=0; i<in.size()-1;i++){ min=Math.min(min, in.get(i)); max = Math.max(in.get(i)- min, max); } return max; } 

}

Answer 13

This is maximum difference between two elements in array and this is my solution:

O(N) time complexity O(1) space complexity

  int[] arr = {5, 4, 6 ,7 ,6 ,3 ,2, 5}; int start = 0; int end = 0; int max = 0; for(int i=1; i<arr.length; i++){ int currMax = arr[i] - arr[i-1]; if(currMax>0){ if((arr[i] -arr[start])>=currMax && ((arr[i] -arr[start])>=(arr[end] -arr[start]))){ end = i; } else if(currMax>(arr[i] -arr[start]) && currMax >(arr[end] - arr[start])){ start = i-1; end = i; } } } max = arr[end] - arr[start]; System.out.println("max: "+max+" start: "+start+" end: "+end); 

Answer 14

For all the answers keeping track of the minimum and maximum elements, that solution is actually an O(n^2) solution. This is because at the end it must be checked whether the maximum occurred after the minimum or not. In case it didn't, further iterations are required until that condition is met, and this leaves a worst-case of O(n^2). And if you want to skip the extra iterations then a lot more space is required. Either way, a no-no as compared to the dynamic programming solution

Answer 15

After failing this in a live coding exam for a FB solutions engineer position I had to solve it in a calm cool atmosphere, so here are my 2 cents:

 var max_profit = 0; var stockPrices = [23,40,21,67,1,50,22,38,2,62]; var currentBestBuy = 0; var currentBestSell = 0; var min = 0; for(var i = 0;i < (stockPrices.length - 1) ; i++){ if(( stockPrices[i + 1] - stockPrices[currentBestBuy] > max_profit) ){ max_profit = stockPrices[i + 1] - stockPrices[currentBestBuy]; currentBestSell = i + 1; } if(stockPrices[i] < stockPrices[currentBestBuy]){ min = i; } if( max_profit < stockPrices[i + 1] - stockPrices[min] ){ max_profit = stockPrices[i + 1] - stockPrices[min]; currentBestSell = i + 1; currentBestBuy = min; } } console.log(currentBestBuy); console.log(currentBestSell); console.log(max_profit); 

Answer 16

The only answer really answering the question is the one of @akash_magoon (and in such a simple way!), but it does not return the exact object specified in the question. I refactored a bit and have my answer in PHP returning just what is asked:

 function maximizeProfit(array $dailyPrices) { $buyDay = $sellDay = $cheaperDay = $profit = 0; for ($today = 0; $today < count($dailyPrices); $today++) { if ($dailyPrices[$today] < $dailyPrices[$cheaperDay]) { $cheaperDay = $today; } elseif ($dailyPrices[$today] - $dailyPrices[$cheaperDay] > $profit) { $buyDay = $cheaperDay; $sellDay = $today; $profit = $dailyPrices[$today] - $dailyPrices[$cheaperDay]; } } return [$buyDay, $sellDay]; }