最大单笔销售利润

小开

最佳答案

我喜欢这个问题。这是一个经典的面试问题，取决于你如何思考，你最终会得到越来越好的解决方案。当然可以在比 O (n²)时间更短的时间内完成，我在这里列出了三种不同的思考问题的方法。希望这能回答你的问题！

首先，分而治之的解决方案。让我们看看是否可以解决这个问题，将输入分成两半，解决每个子数组中的问题，然后将两者结合在一起。事实证明，我们确实可以做到这一点，而且可以高效地做到这一点！直觉是这样的。如果我们有一个单一的一天，最好的选择是买在那一天，然后在同一天卖回来，没有利润。否则，将数组分成两半。如果我们考虑一下最佳答案可能是什么，答案肯定在以下三个地方之一:

正确的买卖对完全发生在上半年。
正确的买卖对完全发生在下半年。
正确的买入/卖出对出现在两个半场——我们在上半场买入，然后在下半场卖出。

我们可以通过在第一部分和第二部分递归调用我们的算法来获得(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) :

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

如果我们用这种方法我们的递回关系式就是

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

在这里使用主定理给我们一个带有 O (lgn)空间的 O (n)运行时，这甚至比我们最初的解决方案还要好！

但是等一下，我们可以做得更好！让我们考虑用动态编程来解决这个问题。我们的想法是这样来考虑这个问题。假设我们在查看了第一个 k 元素之后就知道了问题的答案。我们能否利用我们对(k + 1) st 元素的知识，结合我们的初始解，来解决第一个(k + 1)元素的问题？如果是这样，我们可以得到一个很好的算法，通过解决第一个元素的问题，然后是前两个，然后是前三个，等等，直到我们计算出前 n 个元素。

让我们想想该怎么做。如果我们只有一个元素，我们已经知道它必须是最佳买卖对。现在假设我们已经知道第一个 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 符号中的常数因子，可能会有一些优化，但是除此之外，我们不能指望找到任何彻底更好的选项。

总的来说，这意味着我们有以下算法:

天真: O (n²)时间，O (1)空间。
分而治之: O (n lgn)时间，O (lgn)空间。
优化的分而治之: O (n)时间，O (lgn)空间。
动态规划: 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

小开

这是带有一点间接性的最大和子序列问题。给出了最大和子序列问题的一个整数列表，该整数列表可以是正的，也可以是负的，求该列表的一个连续子集的最大和。

你可以把这个问题转换成那个问题，通过连续几天的盈利或亏损。所以你可以把一个股票价格列表，例如 [5, 6, 7, 4, 2]，转换成一个收益/损失列表，例如 [1, 1, -3, -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 );
}

小开

以下是我的 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);
}

小开

我想出了一个简单的解决方案——代码更加自我解释。这是一个动态编程问题。

代码不会处理错误检查和边缘情况。这只是一个例子，给出了解决这个问题的基本逻辑的想法。

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

小开

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)解决问题。我认为不能再快了。

小开

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

小开

确定最大利润的一种可能性是，在数组中的每个索引处跟踪数组中的左侧最小和右侧最大元素。然后，当您遍历股票价格时，对于任何给定的一天，您都将知道当天的最低价格，并且还将知道当天之后(包括)的最大价格。

例如，让我们定义一个 min_arr和 max_arr，给定的数组是 arr。min_arr中的指数 i将是 arr中所有指数 <= i(包括 i)的最小元素。max_arr中的指数 i是 arr中所有指数 max_arr0(包括 i 的右边)的最大元素。然后，您可以找到 max_arr和‘ 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

这应该在 O (n)时间内运行，但我相信它会占用很多空间。

小开

我不太确定为什么这被认为是一个动态编程问题。我在教科书和算法指南中看到过这个问题，使用 O (n logn)运行时和 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

小开

这是我的解决办法

public static int maxProfit(List<Integer> 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;
}
}

小开

这是一个有趣的问题，因为它的 看起来硬，但仔细思考产生了一个优雅的，精简的解决方案。

如前所述，它可以在 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，那么我们将这个 diff 保持为新的 maxLoss。由于最大指数保证小于当前指数，我们保证“买入”日期小于“卖出”日期。

在计算最大收益的情况下，一切都是相反的。我们跟踪列表中直到当前条目的最小值。我们计算最小值和当前条目之间的差值(将减法的顺序颠倒过来)。如果 current-min > maxGain，那么我们将这个 diff 保留为新的 maxGain。同样，“买入”(min)指数在当前(“卖出”)指数之前。

我们只需要跟踪 maxGain (或 maxLoss) ，以及 min 或 max 的指数，但不能两者兼顾，我们不需要比较指数来验证“买入”小于“卖出”，因为我们很自然地得到了这个结果。

小开

最大单一销售利润，O (n)解

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
}

这里有一个项目，它对 o (N) vs o (n ^ 2)方法进行时间复杂度测试，测试对象是100kint 上的随机数据集。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)方法，它循环遍历每天剩余的日子，双重循环。

小开

这是数组中两个元素之间的最大差值，这是我的解决方案:

O (N)时间复杂度 O (空间复杂度

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

小开

对于跟踪最小和最大元素的所有答案，该解实际上是 O (n ^ 2)解。这是因为在最后必须检查最大值是否发生在最小值之后。如果没有，则需要进一步的迭代，直到满足该条件，这就留下了 O (n ^ 2)的最坏情况。如果您想跳过额外的迭代，那么需要更多的空间。无论哪种方式，与动态编程解决方案相比都是不可取的

小开

在一次 FB 解决方案工程师职位的现场编程考试中失败后，我不得不在一个平静、凉爽的气氛中解决这个问题，所以这里是我的2美分:

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

小开

真正回答这个问题的唯一答案是@akash _ magoon (用这么简单的方式!)，但不返回问题中指定的确切对象。我进行了一些重构，并用 PHP 得到了我的答案，返回的正是所询问的内容:

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

小开

一个简单的解决办法:

+ (int)maxProfit:(NSArray *)prices {
int maxProfit = 0;


int bestBuy = 0;
int bestSell = 0;
int currentBestBuy = 0;


for (int i= 1; i < prices.count; i++) {
int todayPrice = [prices[i] intValue];
int bestBuyPrice = [prices[currentBestBuy] intValue];
if (todayPrice < bestBuyPrice) {
currentBestBuy = i;
bestBuyPrice = todayPrice;
}


if (maxProfit < (todayPrice - bestBuyPrice)) {
bestSell = i;
bestBuy = currentBestBuy;
maxProfit = (todayPrice - bestBuyPrice);
}
}


NSLog(@"Buy Day : %d", bestBuy);
NSLog(@"Sell Day : %d", bestSell);


return maxProfit;
}

小开

投票最多的答案不允许出现利润最大值为负的情况，因此应加以修改，以便考虑到这种情况。可以通过将循环的范围限制在(len (a)-1) ，并通过将指数移动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

小开

def get_max_profit(stock):
p=stock[0]
max_profit=0
maxp=p
minp=p
for i in range(1,len(stock)):
p=min(p,stock[i])
profit=stock[i]-p
if profit>max_profit:
maxp=stock[i]
minp=p
max_profit=profit
return minp,maxp,max_profit






stock_prices = [310,315,275,295,260,270,290,230,255,250]
print(get_max_profit(stock_prices))

Python3中的这个程序可以返回购买价格和销售价格，这将使利润最大化，使用 O (n)的时间复杂性和 O (1)的空间复杂性计算。

小开

多次买卖, 使用下面的代码

时间复杂度 O (n)

n=int(input())
a = list(map(int,input().split()))
m=0
b=a[0]
s=0
for i in range(1,n):
if(a[i]<a[i-1]):
s=a[i-1]
m=m+s-b
b=a[i]
if(a[n-1]>b):
m=m+a[n-1]-b
print(m)