Pythonで解く「株の売買に最適なタイミング II」問題 ― 最大利益を求める貪欲法アルゴリズム

問題概要

配列Aが与えられ、A[i] は i 日目の株価を表すものとします。このとき、達成できる最大の利益を求めます。取引（株の買いと売り）は何度でも行えますが、同時に複数の取引を持つことはできません。つまり、新しい株を購入する前に、必ず保有中の株を売却しておく必要があります。

具体例

例えば、配列が A = [7, 1, 5, 3, 6, 4] の場合、答えは 7 になります。

2日目（インデックス1）に株価 1 で購入し、3日目に株価 5 で売却すると、利益は 5 − 1 = 4。続いて、4日目に株価 3 で再び購入し、5日目に株価 6 で売却すると、利益は 6 − 3 = 3 となります。合計利益は 4 + 3 = 7 です。

解法のアプローチ：貪欲法（グリーディ法）

この問題は貪欲法を使うと非常にシンプルに解けます。考え方は次のとおりです。

隣接する2日の株価を順番に比較し、価格が上昇していた場合はその差額をすべて利益として加算します。「谷で買って山で売る」行動を細かく分割しても、結局はすべての上昇幅の合計と等しくなるため、この手法で最適解が得られます。

アルゴリズムの手順

• 変数 answer を 0 で初期化する
• i を 1 から n−1 まで繰り返す（n は配列Aの要素数）
  • A[i] − A[i−1] > 0 の場合：answer := answer + (A[i] − A[i−1])
• 最後に answer を返す

Pythonでの実装例

それでは、実際のコードを見てみましょう。

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

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

入力と出力

入力：

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

出力：

13

この入力の場合、上昇する区間（2→8、1→5、4→7）の差額を合計すると、最大利益は 13 になります。

計算量の評価

• 時間計算量：O(n) ― 配列を一度だけ走査すればよいため非常に高速です。
• 空間計算量：O(1) ― 追加のデータ構造は不要で、定数個の変数だけで処理できます。

このように、貪欲法を活用すれば複雑な動的計画法を用いなくても、線形時間で最大利益を求めることができます。