Problem
株価の配列があったときに、利益が最大となる買いと売りのタイミングを計算する問題です。
You are given an array prices where prices[i] is the price of a given stock on the ith day.
InputとOutputの例は次になります。
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
利益を最大化するには、なるべく安く買ってなるべく高く売る必要があります。ただし、タイミングとしては、買った日より後に後に売らないといけません。
Key Idea
まずは、買う日と売る日の組み合わせを総当りで調査し、最大利益になる組み合わせを見つける方法があります。(Approach #1)
ただし、それでは時間計算量がO(n^2)となっています。そこで、各日について、下記の２つの変数 A と B を追跡しておけば、各日の株価を一度だけスキャンするだけで、最大の利益を得るための最適な日を見つけることができます。(Approach #2)
A : その日までの最低価格: 株を買う最適な日は、その日までの最低価格の日です。なぜなら、最小の価格で買えば、それが将来的に最大の利益をもたらす可能性があるからです。
B : その日までの最大利益: その日の価格とこれまでの最小価格との差を計算します。この差がこれまでの最大利益を超えていれば、最大利益を更新します。
Approach #1 Brute Force
総当りで組み合わせを考える方法は、下記の様に実装できます。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
max_profit = 0
for i in range(len(prices)-1):
for j in range(i+1, len(prices)):
if prices[j] - prices[i] > max_profit:
max_profit = prices[j] - prices[i]
return max_profit
この解法では、計算量は下記の様になります。
-
Time complexity: O(n^2)。二重ループを利用しています。nは、
pricesの長さです。 -
Space complexity: O(1)。
max_profitという変数しかメモリを使っていません。
Approach #2 One pass
上述のように、その日までの最低価格と最大利益を同時に追跡していきます。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
min_price = float('inf')
max_profit = 0
for i in range(len(prices)):
# 現在の価格が今までの最低価格より安い場合、更新
if prices[i] < min_price:
min_price = prices[i]
# 現在の価格と今までの最低価格の差がこれまでの最大利益を超えている場合、更新
if max_profit < prices[i] - min_price :
max_profit = prices[i] - min_price
return max_profit
min_priceの初期値を無限大で設定している目的は、最初の株価がどんな値であってもそれを新たな min_price（最小価格）として更新できるようにするためです。
この解法では、計算量は下記の様になります。
-
Time complexity: O(n)。一度のスキャンを通じて最安価格と最大利益を同時に追跡しています。
-
Space complexity: O(1)。
min_priceとmax_profitという変数しかメモリを使っていません。
Reference