최대 단일 판매 이익
하루에 주가를 나타내는 N 개의 정수 배열이 있다고 가정 합니다. 우리는 한 쌍의 (buyDay, sellDay) 와, buyDay ≤ sellDay 우리가 주식을 구입 한 경우에, buyDay 하고 판매하는 sellDay , 우리는 우리의 이익을위한 것입니다.
가능한 모든 (buyDay, sellDay) 쌍 을 시도하고 모든 것을 최대한 활용하여 알고리즘에 대한 O (n 2 ) 솔루션 이 있습니다. 그러나 아마도 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 ) 솔루션을 이겼습니다 !
하지만 기다려! 우리는 이것보다 훨씬 더 잘할 수 있습니다. 반복에서 유일한 이유는 각 반에서 최소값과 최대 값을 업무입니다. 우리는 이미 반을 재귀 적으로 탐색하고 있기 때문에 아마도 재귀가 각 반에 일치 최소값과 최대 값을 되돌려 보내면 더 잘 할 수 있습니다! 다시 말해, 우리의 재귀는 다음 세 가지를 뒷받침합니다.
- 구매 및 판매 시간은 이익을 추구합니다.
- 범위의 전체 최소값입니다.
- 범위 내 최대 값입니다.
이 마지막 두 값은 계산 재귀와 언어 수있는 간단한 재귀를 사용하여 재귀 적으로 계산할 수 있습니다 (1).
- 단일 요소 범위의 최대 값과 최소값은 해당 요소입니다.
- 다중 요소 범위의 최대 값과 최소값은 입력을 반으로 나누고 각 절반의 최대 값과 최소값을 다음 추가의 최대 값과 최소값을 가져옵니다.
우리가이를 사용한다면, 우리의 재발 관계는 이제
T(1) <= O(1)
T(n) <= 2T(n / 2) + O(1)
여기서 마스터 정리를 사용하면 O (lg n) 공간이있는 O (n)의 가동이 제공되고, 원래 솔루션보다 훨씬 좋습니다!
그러나 잠깐만-우리는 이것보다 더 잘 할 수 있습니다! 동적 프로그래밍을 사용 하여이 문제를 해결하는 것에 대해 생각해 봅니다. 아이디어는 다음과 같이 문제에 대해 생각하는 것입니다. 첫 번째 k 요소를 살펴본 후 문제에 대한 답을 알고 가정하십시오. 첫 번째 (k + 1) 요소의 문제를 해결하기 위해 초기 솔루션과 결합 된 (k + 1) 요소의 지식을 사용할 수 있습니까? 첫 번째 요소, 첫 번째 요소, 첫 번째 요소 등의 문제를 해결하여 첫 번째 요소에 대해 계산할 때까지 훌륭한 알고리즘을 얻을 수 있습니다.
이 작업을 수행하는 방법에 대해 생각해 보겠습니다. 하나의 요소 만 가지고있는 페어, 우리는 그것이 베스트 바이 / 쌍이어야한다는 것을 이미 알고 있습니다. 이제 첫 번째 k 요소에 가장 생각 답을 알고 (k + 1) 번째 요소를 봅시다. 그런 다음이 값이 첫 번째 k 요소보다 더 나은 솔루션을 만들 수있는 유일한 방법은 첫 번째 k 요소 중 가장 작은 지금과 새 요소의 차이가 계산 한 가장 차이보다 큰 경우입니다. 따라서 이익을 발견 보면서 지금까지 본 최소값과 첫 번째 k 요소만으로도 수있는 수있는 두 가지 값을 추적 가정합니다. 처음에는 지금까지 본 최소값이 첫 번째 요소이며 최대 수익은 0입니다. 새로운 요소가 보이면 우리는 먼저 지금까지 본 최저 가격으로 구매하고 현재 가격으로 판매하여 얼마나 많은 금액을 계산하여 최적의 가격으로 업데이트합니다. 이것이 지금까지 계산 한 최적의 값보다 낫다면이 최적의 솔루션을 업데이트합니다. 다음으로 지금까지 본 최소 요소를 현재 가장 작은 요소와 새 요소의 최소로 업데이트합니다.
각 단계에서 우리는 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 2 ) 시간, 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
이것은 약간의 간접적 인 문제의 최대 합 하위 시퀀스 문제입니다. 최대 서브 시퀀스 문제에는 양수 또는 음수 일 수있는 정수 목록이 제공되고, 해당 목록의 연속 서브 세트의 가장 큰 합을 찾으십시오.
연속적인 일 사이에 손익을 가져 오기가 문제를 그 문제로 간단하게 변환 할 수 있습니다. 따라서 주가리스트를 예 [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 );
}
공동 저자 : https://stackoverflow.com/users/599402/ephraim
문제는
동적 프로그래밍을 사용하여 해결 한 최대 하위 시퀀스와 동일합니다 . 현재 및 이전을 추적합니다 (박사, 구매 날짜 및 판매 날짜) 현재가 이전보다 높으면 이전을 현재로 바꿉니다.
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)의 문제를 해결합니다. 나는 그것이 더 빨리 빨리 수 생각합니다.
것처럼 보이지만 신중하게 생각하면 우아하고 찾기를 얻을 수 있기 때문에 흥미로운 문제 입니다.
언급 한 같이, 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의 색인 만 추적하면 둘다는 아닙니다. '구매'가 '판매'보다 약간 지 확인하기 위해 지수를 필요가 없습니다. 이를 자연스럽게 얻습니다.
최대 단일 판매 이익, 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
}
다음은 100k ints의 임의 데이터 세트에 대한 o (N) 대 o (n ^ 2) 접근 방식의 시간 테스트를 수행하는 프로젝트입니다. O (n ^ 2)는 2 초, O (n)은 0.01 초
https://github.com/gulakov/complexity.js
function stocks_n2(ps){
for (maxDif=0,i=_i=0;p=ps[i++];i=_i++)
for (;p2=ps[i++];)
if (p2-p>maxDif)
maxDif=p2-p
return maxDif
}
이것은 하루의 나머지 날, 이중 루프를 통해 반복되는 느린 방식입니다.
최고 투표 답변은 최대 이익이 음수 인 경우를 허용하지 않을 경우에도 허용되어야합니다. 루프 범위를 (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
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. 인덱스 i는 모든 인덱스 (I의 왼쪽 및 포함) min_arr에 arr, 대한 최소 요소입니다 <= i. 인덱스 i는 모든 인덱스 (I의 권리를 포함하여) max_arr의 최대 요소가됩니다 . 그런 다음 'min_arr' 의 해당 요소 사이의 최대 차이를 수 있습니다 .arr>= imax_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) 시간 숫자 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);
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;
}
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)의 공간을 사용 합니다.
여기 내 해결책이 있습니다.
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 ^ 2)가 남습니다. 추가 반복을 건너 뛰려면 더 많은 공간이 필요합니다. 어느 쪽이든, 동적 프로그래밍 솔루션과 선호 때 아니오
참고 URL : https://stackoverflow.com/questions/7086464/maximum-single-sell-profit
'IT' 카테고리의 다른 글
| 크로스 모듈 변수를 만드는 방법? (0) | 2020.07.18 |
|---|---|
| Bash 루프의 카운터 증가가 작동하지 않습니다. (0) | 2020.07.18 |
| URL에 추가하고 페이지 새로 고침 (0) | 2020.07.18 |
| RESTful POST 메소드에서 다음 변수에 액세스하는 방법 (0) | 2020.07.18 |
| 역 추적 로그 예외 (0) | 2020.07.18 |