BinaryDevelop
  1. ホーム
  2. arrays

[解決済み] 最大単品販売利益

2022-07-18 14:06:51

質問

の配列が与えられたとします。 n の整数の配列が与えられたとする． この配列から (buyDay, sellDay) で、かつ buyDay ≤ sellDay で、もし株を買ったら 買い日 に買って 売り日 で売れば、利益が最大になります。

明らかに O(n 2 ) をすべて試すことで、アルゴリズムの解を求めることができます。 (buyDay, sellDay) のペアを試し、それらのすべてから最良のものを選ぶというものです。 しかし、もっと良いアルゴリズムがあるでしょうか。 O(n) 時間で実行できるような、より優れたアルゴリズムはないでしょうか？

どのように解決するのですか？

私はこの問題が大好きです。 古典的な面接の質問で、どう考えるかによって、どんどん良い解答が得られることになります。 確かに、O(n)よりも良い時間でこれを行うことは可能です。 2 この問題について考えられる3つの異なる方法をここにリストアップしました。 これがあなたの質問の答えになることを願っています。

まず、分割して解く方法です。 入力を半分に分割し、それぞれのサブアレイで問題を解き、それから 2 つを結合することで解決できるかどうかを見てみましょう。 実際にこれができて、しかも効率よく解けることがわかりました。 直感的には次のような感じです。 もし1日だけなら、その日に買って、同じ日に売り戻して利益を得るのが最良の選択である。 そうでなければ、配列を半分に分ける。 最適な答えは何かと考えると、3つのうちのどれかになるはずです。

  1. 正しい買い/売りのペアは、完全に前半の中で発生します。
  2. 正しい売り買いのペアは、完全に後半に発生します。
  3. 正しい売買のペアが両方の半分にわたって発生する - 前半で購入し、後半で売却します。

前半と後半のアルゴリズムを再帰的に呼び出すことで、(1)と(2)の値を得ることができます。 (3)については、前半の最も低いところで買い、後半の最も高いところで売るのが最も利益を上げる方法となります。 入力に対して単純な線形スキャンを行い、2つの値を見つけるだけで、前半と後半の最小値と最大値を見つけることができます。 すると、次のような再帰を持つアルゴリズムが得られます。 

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

を使うことで マスター定理 を使って再帰を解くと、O(n lg n)時間で実行でき、再帰呼び出しのためにO(lg n)空間を使用することがわかります。 私たちは、素朴なO(n 2 の解決策を打ち破りました!

しかし、待ってください! これよりもっとうまくいくはずです。 再帰で O(n) 項がある唯一の理由は、各半分の最小値と最大値を見つけるために入力全体をスキャンしなければならなかったことに注意してください。 すでに各半分を再帰的に探索しているのだから、各半分に格納されている最小値と最大値を再帰的に返すようにすれば、もっとうまくいくかもしれない! 言い換えれば、この再帰は3つのものを手渡します。

  1. 利益を最大化するための買い時および売り時。
  2. 範囲内の全体の最小値。
  3. 範囲内の全体の最大値です。

これらの最後の2つの値は、(1)を計算する再帰と同時に実行できる簡単な再帰を使用して再帰的に計算することができます。

  1. 単一要素の範囲の最大値と最小値は、その要素だけです。
  2. 複数要素の範囲の最大値と最小値は、入力を半分に分割し、それぞれの半分の最大値と最小値を見つけ、そしてそれぞれの最大値と最小値を取ることによって見つけることができます。

このアプローチを使用する場合、漸化式は次のようになります。 

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

マスターの定理を用いると、O(n)の実行時間とO(lg n)の空間が得られ、これは私たちのオリジナルの解決策よりもさらに良いものです!

しかし、ちょっと待ってください！これよりもっと良い方法があるのです。 この問題を動的計画法を使って解決することを考えてみましょう。 この問題を次のように考えるのです。 最初のk個の要素を見て、問題の答えがわかったとします。 (k+1)番目の要素に関する知識と最初の解答を組み合わせて、最初の(k+1)個の要素に関する問題を解くことはできないだろうか？ もしそうなら，最初の要素について問題を解き，次に最初の2つの要素について，そして最初の3つの要素について...と，最初のn個の要素について計算するまで，素晴らしいアルゴリズムを得ることができるだろう．

どうすればいいか考えてみましょう。 要素が1つだけなら、それが最適な売り買いのペアでなければならないことは、すでに分かっています。 ここで、最初のk個の要素について最適解がわかっていて、(k+1)番目の要素に注目したとします。 この値が、最初のk個の要素で得たものより良い解を生み出すことができるのは、最初のk個の要素のうち最小の要素とその新しい要素との差が、これまでに計算した最大の差よりも大きい場合だけです。 そこで、要素を渡り歩くときに、2つの値を記録しておくことにします。これまでに見た最小値と、最初の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)未満の時間を使用する場合、大きな入力ですべての数字を見ることができないので、最適な答えを見逃さないという保証はありません(見ていない要素にquot;hide"するだけかもしれないのです)。 さらに、O(1)以下の空間は使えません。 big-O記法に隠された定数要素にいくつかの最適化があるかもしれませんが、そうでなければ、根本的に良い選択肢を見つけることは期待できません。

全体として、これは次のようなアルゴリズムがあることを意味します。

  • ナイーブ O(n 2 ) 時間、O(1) 空間。
  • 分割統治（Divide-and-Conquer）。O(n lg n)時間、O(lg n)空間。
  • 最適化されたDivide-and-Conquer。O(n)時間、O(lg n)空間。
  • 動的計画法。O(n)時間、O(1)空間。

これが役に立つといいのですが!

EDIT : もし興味があるのなら、私がコード化した これらの4つのアルゴリズムのPython版 を用意しましたので、それらを使って遊んでみて、相対的なパフォーマンスを判断することができます。以下はそのコードです。 


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

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

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

    return bestProfit

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

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

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

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

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

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

def OptimizedDivideAndConquerSingleSellProfit(arr):
    # If the array is empty, the maximum profit is zero.
    if len(arr) == 0:
        return 0

    # This recursive helper function implements the above recurrence.  It
    # returns a triple of (max profit, min array value, max array value).  For
    # efficiency reasons, we always reuse the array and specify the bounds as
    # [lhs, rhs]
    def Recursion(arr, lhs, rhs):
        # If the array has just one element, we return that the profit is zero
        # but the minimum and maximum values are just that array value.
        if lhs == rhs:
            return (0, arr[lhs], arr[rhs])

        # Recursively compute the values for the first and latter half of the
        # array.  To do this, we need to split the array in half.  The line
        # below accomplishes this in a way that, if ported to other languages,
        # cannot result in an integer overflow.
        mid = lhs + (rhs - lhs) / 2
        
        # Perform the recursion.
        ( leftProfit,  leftMin,  leftMax) = Recursion(arr, lhs, mid)
        (rightProfit, rightMin, rightMax) = Recursion(arr, mid + 1, rhs)

        # Our result is the maximum possible profit, the minimum of the two
        # minima we've found (since the minimum of these two values gives the
        # minimum of the overall array), and the maximum of the two maxima.
        maxProfit = max(leftProfit, rightProfit, rightMax - leftMin)
        return (maxProfit, min(leftMin, rightMin), max(leftMax, rightMax))

    # Using our recursive helper function, compute the resulting value.
    profit, _, _ = Recursion(arr, 0, len(arr) - 1)
    return profit

# At this point we've traded our O(n^2)-time, O(1)-space solution for an O(n)-
# time, O(log n) space solution.  But can we do better than this?
#
# To find a better algorithm, we'll need to switch our line of reasoning.
# Rather than using divide-and-conquer, let's see what happens if we use
# dynamic programming.  In particular, let's think about the following problem.
# If we knew the maximum single-sell profit that we could get in just the first
# k array elements, could we use this information to determine what the
# maximum single-sell profit would be in the first k + 1 array elements?  If we
# could do this, we could use the following algorithm:
#
#   Find the maximum single-sell profit to be made in the first 1 elements.
#   For i = 2 to n:
#      Compute the maximum single-sell profit using the first i elements.
#
# How might we do this?  One intuition is as follows.  Suppose that we know the
# maximum single-sell profit of the first k elements.  If we look at k + 1
# elements, then either the maximum profit we could make by buying and selling
# within the first k elements (in which case nothing changes), or we're
# supposed to sell at the (k + 1)st price.  If we wanted to sell at this price
# for a maximum profit, then we would want to do so by buying at the lowest of
# the first k + 1 prices, then selling at the (k + 1)st price.
#
# To accomplish this, suppose that we keep track of the minimum value in the
# first k elements, along with the maximum profit we could make in the first
# k elements.  Upon seeing the (k + 1)st element, we update what the current
# minimum value is, then update what the maximum profit we can make is by
# seeing whether the difference between the (k + 1)st element and the new
# minimum value is.  Note that it doesn't matter what order we do this in; if
# the (k + 1)st element is the smallest element so far, there's no possible way
# that we could increase our profit by selling at that point.
#
# To finish up this algorithm, we should note that given just the first price,
# the maximum possible profit is 0.
#
# This gives the following simple and elegant algorithm for the maximum single-
# sell profit problem:
#
#   Let profit = 0.
#   Let min = arr[0]
#   For k = 1 to length(arr):
#       If arr[k] < min, set min = arr[k]
#       If profit < arr[k] - min, set profit = arr[k] - min
#
# This is short, sweet, and uses only O(n) time and O(1) memory.  The beauty of
# this solution is that we are quite naturally led there by thinking about how
# to update our answer to the problem in response to seeing some new element.
# In fact, we could consider implementing this algorithm as a streaming
# algorithm, where at each point in time we maintain the maximum possible
# profit and then update our answer every time new data becomes available.
#
# The final version of this algorithm is shown here:

def DynamicProgrammingSingleSellProfit(arr):
    # If the array is empty, we cannot make a profit.
    if len(arr) == 0:
        return 0

    # Otherwise, keep track of the best possible profit and the lowest value
    # seen so far.
    profit = 0
    cheapest = arr[0]

    # Iterate across the array, updating our answer as we go according to the
    # above pseudocode.
    for i in range(1, len(arr)):
        # Update the minimum value to be the lower of the existing minimum and
        # the new minimum.
        cheapest = min(cheapest, arr[i])

        # Update the maximum profit to be the larger of the old profit and the
        # profit made by buying at the lowest value and selling at the current
        # price.
        profit = max(profit, arr[i] - cheapest)

    return profit

# To summarize our algorithms, we have seen
#
# Naive:                        O(n ^ 2)   time, O(1)     space
# Divide-and-conquer:           O(n log n) time, O(log n) space
# Optimized divide-and-conquer: O(n)       time, O(log n) space
# Dynamic programming:          O(n)       time, O(1)     space

関連

最新

おすすめ

について
/
プライバシー・ポリシー
/
お問い合わせ
© 2022 BinaryDevelop. すべての権利は、それぞれの所有者に帰属します