Pythonで株の売買に最適なタイミングを見つける！最大利益を求めるアルゴリズム

問題概要

ある配列 A が与えられ、A[i] は i 日目における特定の銘柄の株価を表しているものとします。このとき、得られる最大の利益を求めるのが目的です。取引（株の購入と売却の一連の操作）は最大でも1回しか行えません。

また、複数の取引を同時に抱えることはできないため、新しい株を購入する前に、必ず現在保有している株を売却しておかなければならない点にも注意が必要です。

例として、配列が A = [7, 1, 5, 3, 6, 4] の場合を考えてみましょう。このとき答えは 5 となります。2日目（インデックス1）に株価 1 で株を買い、5日目に株価 6 で売却すれば、利益は 6 − 1 = 5 となるためです。

解法のアプローチ

この問題は、「左から見たときの最小購入価格」と「右から見たときの最大売却価格」をそれぞれ事前に計算しておくことで、効率よく解くことができます。手順は以下の通りです。

• A と同じサイズの2つの配列 leftMin と rightMax を作成し、0 で初期化する
• leftMin[0] = A[0] と設定し、i を 1 から A の長さ − 1 まで順に処理して、leftMin[i] = min(leftMin[i − 1], A[i]) を求める（各日までの最安値）
• rightMax[n − 1] = A[n − 1] と設定し、i を A の長さ − 2 から 0 まで逆順に処理して、rightMax[i] = max(rightMax[i + 1], A[i]) を求める（各日以降の最高値）
• answer := 0 で初期化する
• i を 0 から A の長さ − 2 まで動かしながら、answer := max(answer, rightMax[i + 1] − leftMin[i]) を更新する
• 最後に answer を返す

考え方のポイント

leftMin には「その日までの過去の最安値」、rightMax には「その日以降の未来の最高値」が格納されます。分割地点 i ごとに「i 日目以前に買って、i 日目以降に売る」というパターンの利益 rightMax[i + 1] − leftMin[i] を計算すれば、すべての買い・売りの組み合わせを網羅でき、最大利益が求まります。

Pythonでの実装例

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if not prices:
            return 0
        leftMin, rightMax = [0 for i in range(len(prices))], [0 for i in range(len(prices))]
        leftMin[0] = prices[0]
        for i in range(1, len(prices)):
            leftMin[i] = min(leftMin[i-1], prices[i])
        rightMax[-1] = prices[-1]
        for i in range(len(prices)-2, -1, -1):
            rightMax[i] = max(rightMax[i+1], prices[i])
        ans = 0
        for i in range(len(prices)-1):
            ans = max(ans, rightMax[i+1]-leftMin[i])
        return ans

ob1 = Solution()
print(ob1.maxProfit([7,2,5,8,6,3,1,4,5,4,7]))

入力

prices = [7, 2, 5, 8, 6, 3, 1, 4, 5, 4, 7]

出力

6

この入力の場合、「2日目に価格 2 で買って4日目に価格 8 で売る」か、「7日目に価格 1 で買って11日目に価格 7 で売る」ことで利益 6 が達成できます。

計算量について

このアルゴリズムは配列を数回走査するだけで済むため、時間計算量は O(n)、補助配列を使用することから空間計算量も O(n) となります。全ての買い・売りのペアを総当たりで調べる全探索（O(n²)）と比べ、大幅に効率的である点が大きな魅力です。