Предположим, нам задан массив из n целых чисел, представляющих цены на акции за один день. Мы хотим найти пару (buyDay, sellDay) с buyDay & le; sellDay, так что, если бы мы купили акции на buyDay и продали их на sellDay, мы бы максимизировали нашу прибыль.
Ясно, что алгоритм имеет решение O (n 2), опробовав все возможные пары buyDay, sellDay и максимально используя их. Однако существует ли лучший алгоритм, возможно, тот, который работает в O (n) времени?
Мне нравится эта проблема. Это классический вопрос для интервью и в зависимости от того, как вы думаете об этом, вы получите лучшие и лучшие решения. Это, безусловно, возможно сделать это лучше, чем O (n 2), и я перечислил три разных способа, которыми вы можете думать о проблеме здесь. Надеюсь, это ответит на ваш вопрос!
Во-первых, решение "разделяй и властвуй". Давайте посмотрим, сможем ли мы решить это, разделив вход пополам, решая проблему в каждом подмассиве, а затем объединим два вместе. Оказывается, мы действительно можем это сделать и можем делать это эффективно! Интуиция такова. Если у нас будет один день, лучший вариант - купить в этот день, а затем продать его в тот же день без прибыли. В противном случае разделите массив на две половины. Если мы подумаем о том, каким может быть оптимальный ответ, он должен находиться в одном из трех мест:
Мы можем получить значения для (1) и (2) путем рекурсивного вызова нашего алгоритма на первой и второй половинах. Для варианта (3) способ получить максимальную прибыль - это купить в самой низкой точке в первом тайме и продать в наибольшей точке во второй половине. Мы можем найти минимальные и максимальные значения в двух половинах, просто выполнив простое линейное сканирование по входу и найдем два значения. Тогда это дает нам алгоритм со следующей рекуррентностью:
T(1) <= O(1)
T(n) <= 2T(n / 2) + O(n)
Используя Мастер-теорему, чтобы решить эту проблему, получим, что это выполняется в O (n lg n) времени и будет использовать O (lg n) для рекурсивных вызовов. Мы только что избили наивное решение O (n 2)!
Но подождите! Мы можем сделать гораздо лучше, чем это. Обратите внимание, что единственная причина, по которой мы имеем O (n) -терминал в нашем повторении, состоит в том, что нам пришлось сканировать весь вход, пытаясь найти минимальное и максимальное значения в каждой половине. Поскольку мы уже рекурсивно исследуем каждую половину, возможно, мы можем добиться большего, если рекурсия также вернет минимальные и максимальные значения, сохраненные в каждой половине! Другими словами, наша рекурсия возвращает три вещи:
Эти последние два значения можно вычислить рекурсивно, используя прямую рекурсию, которую мы можем запустить одновременно с рекурсией для вычисления (1):
Если мы используем этот подход, наше рекуррентное соотношение теперь
T(1) <= O(1)
T(n) <= 2T(n / 2) + O(1)
Используя основную теорему, мы получаем время выполнения O (n) с пространством O (lg n), что даже лучше нашего исходного решения!
Но подождите минутку - мы можем сделать еще лучше, чем это! Подумайте о решении этой проблемы с помощью динамического программирования. Идея состоит в том, чтобы думать о проблеме следующим образом. Предположим, что мы знали ответ на проблему, посмотрев на первые k элементов. Можем ли мы использовать наше знание элемента (k + 1) st в сочетании с нашим начальным решением для решения проблемы для первых (k + 1) элементов? Если это так, мы могли бы получить отличный алгоритм, решая проблему для первого элемента, затем первые два, затем первые три и т.д., Пока не вычислим его для первых n элементов.
Подумайте о том, как это сделать. Если у нас есть только один элемент, мы уже знаем, что это должна быть лучшая пара buy/sell. Предположим теперь, что мы знаем лучший ответ для первых 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, но в противном случае мы не можем ожидать найти радикально лучшие варианты.
В целом, это означает, что мы имеем следующие алгоритмы:
Надеюсь, это поможет!
EDIT. Если вам интересно, я закодировал версию этих четырех алгоритмов 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 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 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 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 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 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 see what happens if we use
# dynamic programming. In particular, let 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 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]. Проблема суммы подпоследовательности тогда довольно легко решить: Найти подпоследовательность с наибольшей суммой элементов в массиве
Я не уверен, почему это считается вопросом динамического программирования. Я видел этот вопрос в учебниках и алгоритмах, используя O (n log n), и O (log n) для пробела (например, Elements of Programming Interviews). Это кажется гораздо более простой проблемой, чем люди делают это.
Это работает, отслеживая максимальную прибыль, минимальную цену покупки и, следовательно, оптимальную цену покупки/продажи. Когда он проходит через каждый элемент массива, он проверяет, меньше ли данный элемент, чем минимальная покупательная цена. Если это так, минимальный индекс покупной цены (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 );
}
вот мое решение для 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);
}
Проблема идентична максимальной подпоследовательности Я решил это с помощью динамического программирования. Следите за текущей и предыдущей (прибыль, день продажи и продажи) Если ток выше предыдущего, замените предыдущий на текущий.
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 );
}
Я придумал простое решение - код более понятен. Это один из вопросов динамического программирования.
Код не заботится об ошибках и краях. Его просто образец, чтобы дать идею базовой логики решить проблему.
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). Я думаю, что это невозможно сделать быстрее.
Это интересная проблема, потому что это кажется трудным, но тщательное мышление дает элегантное, упрощенное решение.
Как уже отмечалось, его можно решить с помощью грубой силы в O (N ^ 2) времени. Для каждой записи в массиве (или списке), итерации по всем предыдущим записям, чтобы получить min или max в зависимости от того, найти ли проблему наибольший коэффициент усиления или потери.
Здесь, как думать о решении в O (N): каждая запись представляет собой новый возможный максимум (или мин). Затем все, что нам нужно сделать, это сохранить предыдущий мин (или максимум) и сравнить diff с током и предыдущим мин (или max). Легкий peasy.
Вот код в 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 гарантированно меньше, чем индекс тока, мы гарантируем, что дата "buy" меньше даты "sell".
В случае вычисления наибольшего коэффициента усиления все меняется на противоположное. Мы отслеживаем мин в списке до текущей записи. Мы вычисляем разность между минимумом и током (изменяем порядок в вычитании). Если current - min > maxGain, то мы сохраняем этот diff как новый maxGain. Опять же, индекс "buy" (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), приближается к набору случайных данных на 100k ints. 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) подход, который проходит через остальные дни для каждого дня, двойной цикл.
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");
}
Возможность определить максимальную прибыль может состоять в том, чтобы отслеживать минимальные и правые максимальные элементы левой стороны в массиве по каждому индексу в массиве. Когда вы будете итерировать по ценам на акции, за любой день вы будете знать самую низкую цену до этого дня, и вы также будете знать максимальную цену после (и в том числе) в тот день.
Например, определим a min_arr и max_arr, причем данный массив будет arr. Индекс i в min_arr будет минимальным элементом в arr для всех индексов <= i (слева и включительно i). Индекс i в max_arr будет максимальным элементом в arr для всех индексов >= i (справа и справа от 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) времени, но я считаю, что он использует много места.
Здесь мое решение
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;
}
}
Это максимальная разница между двумя элементами массива, и это мое решение:
O (N) временная сложность O (1) сложность пространства
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];
}