Максимальная прибыль от одной продажи

Question

Предположим, нам дан массив из n целых чисел, представляющих цены акций за один день. Мы хотим найти пару (buyDay, sellDay) , с buyDay & le; sellDay , такой, что если бы мы купили акцию buyDay и продали ее sellDay , мы получили бы максимальную прибыль.

Очевидно, что существует O (n ² ) решение алгоритма, опробовав все возможные пары (buyDay, sellDay) и выбрав лучшее из из всех них. Однако есть ли лучший алгоритм, возможно, который работает за O (n) время?

Answer 1

Мне нравится эта проблема. Это классический вопрос для собеседования, и в зависимости от того, как вы об этом думаете, вы в конечном итоге получите все более и более лучшие решения. Конечно, это можно сделать быстрее, чем за O (n ² ), и я перечислил три разных способа решения проблемы здесь. Надеюсь, это ответит на ваш вопрос!

Во-первых, решение «разделяй и властвуй». Давайте посмотрим, сможем ли мы решить эту проблему, разделив входные данные пополам, решив проблему в каждом подмассиве, а затем объединив их вместе. Оказывается, мы действительно можем сделать это и можем сделать это эффективно! Интуиция заключается в следующем. Если у нас есть один день, лучший вариант - купить в этот день, а затем продать его в тот же день без прибыли. В противном случае разделите массив на две половины. Если мы думаем о том, каким может быть оптимальный ответ, он должен быть в одном из трех мест:

1. Правильная пара покупки / продажи полностью возникает в первой половине.
2. Правильная пара покупки / продажи полностью возникает во второй половине.
3. Правильная пара покупки / продажи происходит на обеих половинах - мы покупаем в первой половине, а затем продаем во второй половине.

Мы можем получить значения для (1) и (2), рекурсивно вызывая наш алгоритм на первой и второй половинках. Для варианта (3) способ получить наибольшую прибыль состоял бы в том, чтобы купить в самой низкой точке в первой половине и продать в самой большой точке во второй половине. Мы можем найти минимальные и максимальные значения в двух половинах, просто выполнив простое линейное сканирование ввода и найдя два значения. Это тогда дает нам алгоритм со следующим повторением:

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

Используя основную теорему для решения рекуррентности, мы обнаруживаем, что она выполняется за O (n lg n) времени и будет использовать пространство O (lg n) для рекурсивных вызовов. Мы только что победили наивное решение O (n ² )!

Но подождите! Мы можем сделать намного лучше, чем это. Обратите внимание, что единственная причина, по которой в нашем повторении есть термин 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). Может быть некоторая оптимизация для постоянных факторов, скрытых в нотации big-O, но в противном случае мы не можем ожидать каких-либо радикально лучших вариантов.

В целом это означает, что у нас есть следующие алгоритмы:

• Наивный: O (n ² ) времени, O (1) пробел.
• Разделяй и властвуй: O (n lg n) время, O (lg n) пространство.
• Оптимизированный метод «разделяй и властвуй»: время O (n), пространство O (lg n).
• Динамическое программирование: O (n) время, O (1) пробел.

Надеюсь, это поможет!

РЕДАКТИРОВАТЬ : Если вам интересно, я кодировал Python-версию этих четырех алгоритмов , чтобы вы могли поиграть с ними и оценивать их относительные характеристики. Вот код:

# Four different algorithms for solving the maximum single-sell profit problem,
# each of which have different time and space complexity.  This is one of my
# all-time favorite algorithms questions, since there are so many different
# answers that you can arrive at by thinking about the problem in slightly
# different ways.
#
# The maximum single-sell profit problem is defined as follows.  You are given
# an array of stock prices representing the value of some stock over time.
# Assuming that you are allowed to buy the stock exactly once and sell the
# stock exactly once, what is the maximum profit you can make?  For example,
# given the prices
#
#                        2, 7, 1, 8, 2, 8, 4, 5, 9, 0, 4, 5
#
# The maximum profit you can make is 8, by buying when the stock price is 1 and
# selling when the stock price is 9.  Note that while the greatest difference
# in the array is 9 (by subtracting 9 - 0), we cannot actually make a profit of
# 9 here because the stock price of 0 comes after the stock price of 9 (though
# if we wanted to lose a lot of money, buying high and selling low would be a
# great idea!)
#
# In the event that there's no profit to be made at all, we can always buy and
# sell on the same date.  For example, given these prices (which might
# represent a buggy-whip manufacturer:)
#
#                            9, 8, 7, 6, 5, 4, 3, 2, 1, 0
#
# The best profit we can make is 0 by buying and selling on the same day.
#
# Let's begin by writing the simplest and easiest algorithm we know of that
# can solve this problem - brute force.  We will just consider all O(n^2) pairs
# of values, and then pick the one with the highest net profit.  There are
# exactly n + (n - 1) + (n - 2) + ... + 1 = n(n + 1)/2 different pairs to pick
# from, so this algorithm will grow quadratically in the worst-case.  However,
# it uses only O(1) memory, which is a somewhat attractive feature.  Plus, if
# our first intuition for the problem gives a quadratic solution, we can be
# satisfied that if we don't come up with anything else, we can always have a
# polynomial-time solution.

def BruteForceSingleSellProfit(arr):
    # Store the best possible profit we can make; initially this is 0.
    bestProfit = 0;

    # Iterate across all pairs and find the best out of all of them.  As a
    # minor optimization, we don't consider any pair consisting of a single
    # element twice, since we already know that we get profit 0 from this.
    for i in range(0, len(arr)):
        for j in range (i + 1, len(arr)):
            bestProfit = max(bestProfit, arr[j] - arr[i])

    return bestProfit

# This solution is extremely inelegant, and it seems like there just *has* to
# be a better solution.  In fact, there are many better solutions, and we'll
# see three of them.
#
# The first insight comes if we try to solve this problem by using a divide-
# and-conquer strategy.  Let's consider what happens if we split the array into
# two (roughly equal) halves.  If we do so, then there are three possible
# options about where the best buy and sell times are:
#
# 1. We should buy and sell purely in the left half of the array.
# 2. We should buy and sell purely in the right half of the array.
# 3. We should buy in the left half of the array and sell in the right half of
#    the array.
#
# (Note that we don't need to consider selling in the left half of the array
# and buying in the right half of the array, since the buy time must always
# come before the sell time)
#
# If we want to solve this problem recursively, then we can get values for (1)
# and (2) by recursively invoking the algorithm on the left and right
# subarrays.  But what about (3)?  Well, if we want to maximize our profit, we
# should be buying at the lowest possible cost in the left half of the array
# and selling at the highest possible cost in the right half of the array.
# This gives a very elegant algorithm for solving this problem:
#
#    If the array has size 0 or size 1, the maximum profit is 0.
#    Otherwise:
#       Split the array in half.
#       Compute the maximum single-sell profit in the left array, call it L.
#       Compute the maximum single-sell profit in the right array, call it R.
#       Find the minimum of the first half of the array, call it Min
#       Find the maximum of the second half of the array, call it Max
#       Return the maximum of L, R, and Max - Min.
#
# Let's consider the time and space complexity of this algorithm.  Our base
# case takes O(1) time, and in our recursive step we make two recursive calls,
# one on each half of the array, and then does O(n) work to scan the array
# elements to find the minimum and maximum values.  This gives the recurrence
#
#    T(1)     = O(1)
#    T(n / 2) = 2T(n / 2) + O(n)
#
# Using the Master Theorem, this recurrence solves to O(n log n), which is
# asymptotically faster than our original approach!  However, we do pay a
# (slight) cost in memory usage.  Because we need to maintain space for all of
# the stack frames we use.  Since on each recursive call we cut the array size
# in half, the maximum number of recursive calls we can make is O(log n), so
# this algorithm uses O(n log n) time and O(log n) memory.

def DivideAndConquerSingleSellProfit(arr):
    # Base case: If the array has zero or one elements in it, the maximum
    # profit is 0.
    if len(arr) <= 1:
        return 0;

    # Cut the array into two roughly equal pieces.
    left  = arr[ : len(arr) / 2]
    right = arr[len(arr) / 2 : ]

    # Find the values for buying and selling purely in the left or purely in
    # the right.
    leftBest  = DivideAndConquerSingleSellProfit(left)
    rightBest = DivideAndConquerSingleSellProfit(right)

    # Compute the best profit for buying in the left and selling in the right.
    crossBest = max(right) - min(left)

    # Return the best of the three
    return max(leftBest, rightBest, crossBest)

# While the above algorithm for computing the maximum single-sell profit is
# better timewise than what we started with (O(n log n) versus O(n^2)), we can
# still improve the time performance.  In particular, recall our recurrence
# relation:
#
#    T(1) = O(1)
#    T(n) = 2T(n / 2) + O(n)
#
# Here, the O(n) term in the T(n) case comes from the work being done to find
# the maximum and minimum values in the right and left halves of the array,
# respectively.  If we could find these values faster than what we're doing
# right now, we could potentially decrease the function's runtime.
#
# The key observation here is that we can compute the minimum and maximum
# values of an array using a divide-and-conquer approach.  Specifically:
#
#    If the array has just one element, it is the minimum and maximum value.
#    Otherwise:
#       Split the array in half.
#       Find the minimum and maximum values from the left and right halves.
#       Return the minimum and maximum of these two values.
#
# Notice that our base case does only O(1) work, and our recursive case manages
# to do only O(1) work in addition to the recursive calls.  This gives us the
# recurrence relation
#
#    T(1) = O(1)
#    T(n) = 2T(n / 2) + O(1)
#
# Using the Master Theorem, this solves to O(n).
#
# How can we make use of this result?  Well, in our current divide-and-conquer
# solution, we split the array in half anyway to find the maximum profit we
# could make in the left and right subarrays.  Could we have those recursive
# calls also hand back the maximum and minimum values of the respective arrays?
# If so, we could rewrite our solution as follows:
#
#    If the array has size 1, the maximum profit is zero and the maximum and
#       minimum values are the single array element.
#    Otherwise:
#       Split the array in half.
#       Compute the maximum single-sell profit in the left array, call it L.
#       Compute the maximum single-sell profit in the right array, call it R.
#       Let Min be the minimum value in the left array, which we got from our
#           first recursive call.
#       Let Max be the maximum value in the right array, which we got from our
#           second recursive call.
#       Return the maximum of L, R, and Max - Min for the maximum single-sell
#           profit, and the appropriate maximum and minimum values found from
#           the recursive calls.
#
# The correctness proof for this algorithm works just as it did before, but now
# we never actually do a scan of the array at each step.  In fact, we do only
# O(1) work at each level.  This gives a new recurrence
#
#     T(1) = O(1)
#     T(n) = 2T(n / 2) + O(1)
#
# Which solves to O(n).  We're now using O(n) time and O(log n) memory, which
# is asymptotically faster than before!
#
# The 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

Это проблема подпоследовательности максимальной суммы с некоторой косвенностью. Задача подпоследовательности максимальной суммы задается списком целых чисел, которые могут быть положительными или отрицательными, найти наибольшую сумму непрерывного подмножества этого списка.

Вы можете легко преобразовать эту проблему в эту проблему, беря прибыль или убыток между последовательными днями. Таким образом, вы бы преобразовали список цен на акции, например, [5, 6, 7, 4, 2] в список прибылей / убытков, например, [1, 1, -3, -2]. Тогда проблему суммы подпоследовательностей решить довольно просто: Найти подпоследовательность с наибольшей суммой элементов в массиве

Answer 3

Я не совсем уверен, почему это считается вопросом динамического программирования. Я видел этот вопрос в учебниках и руководствах по алгоритмам, используя 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

Answer 4

Вот мое решение 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);     
}

Answer 5

Проблема идентична максимальной подпоследовательности
Я решил это с помощью динамического программирования. Следите за текущим и предыдущим (прибыль, дата покупки и продажи) Если ток выше предыдущего, замените предыдущий на текущий.

    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

Максимальная прибыль от одной продажи, решение 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) и o (n ^ 2)на случайный набор данных на 100 тыс. 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) двойной цикл, повторяющий остаток дней для каждого дня.

Answer 7

Это интересная проблема, потому что кажется трудным, но осторожное мышление дает элегантное, урезанное решение.

Как уже отмечалось, его можно решить грубой силой за 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. Поскольку индекс max гарантированно будет меньше индекса текущего, мы гарантируем, что дата «покупки» будет меньше даты «продажи».

В случае расчета наибольшего усиления все меняется на противоположное. Мы отслеживаем мин в списке до текущей записи. Мы рассчитываем разницу между минимальной и текущей записью (обратный порядок вычитания). Если current - min> maxGain, то мы сохраняем этот diff как новый maxGain. Опять же, индекс «покупка» (мин) предшествует индексу текущего («продажа»).

Нам нужно только отслеживать maxGain (или maxLoss) и индекс min или max, но не оба, и нам не нужно сравнивать индексы, чтобы проверить, что «buy» меньше, чем «sell» , поскольку мы получаем это естественно.

Answer 8

Ответ с наибольшим количеством голосов не учитывает случаи, в которых максимальная прибыль отрицательна, и должен быть изменен для учета таких случаев. Это можно сделать, ограничив диапазон цикла (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

Answer 9

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).Я думаю, что это не может быть сделано быстрее.

Answer 10

Я пришел к простому решению - код больше не требует пояснений.Это один из тех вопросов динамического программирования.

Код не заботится о проверке ошибок и крайних случаях.Это просто пример, чтобы дать представление о базовой логике для решения проблемы.

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