Pythonで株の複数回売買による最大利益を求めるプログラム

時系列順に並んだ企業の株価リストが与えられたとします。このとき、その株式を何度でも自由に売買して得られる最大の利益を求める必要があります。ただし、株式は必ず「購入してから売却する」という順序で取引しなければならない点に注意してください。

例えば、入力が prices = [10, 50, 30, 40, 60] の場合、出力は 70 になります。これは、10で購入して50で売却し、その後30で再度購入して60で売却することで、合計70の利益を得られるためです。

解法のアプローチ

この問題は「貪欲法(グリーディー法)」を使うことで、非常にシンプルかつ効率的に解くことができます。手順は以下の通りです。

• prev_price(前回の価格)を無限大(float("inf"))で初期化する
• profit(利益)を 0 で初期化する
• prices の各要素 p について以下を繰り返す:
  • p が prev_price より大きい場合、profit に p - prev_price(値上がり分)を加算する
• ループの最後で prev_price を p に更新する
• すべての処理が終わったら profit を返す

なぜこの方法で正しい答えが得られるのか

価格が前回より上昇したタイミングで、その差額をすべて利益として加算していくのがポイントです。これは、実際に「安いときに買って、高いときに売る」という取引を繰り返した場合と数学的に同じ結果になります。連続する値上がりも自動的に合算されるため、複雑なケースでも最適解が求められます。

計算量は配列を一度だけ走査するため O(n)、追加のメモリは不要で O(1) と、どちらも非常に効率的です。

Pythonでの実装例

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

class Solution:
    def solve(self, prices):
        prev_price = float("inf")
        profit = 0
        for p in prices:
            if p > prev_price:
                profit += p - prev_price
            prev_price = p
        return profit

ob = Solution()
print(ob.solve([10, 50, 30, 40, 60]))

入力

[10, 50, 30, 40, 60]

出力

70

まとめ

株価の複数回売買による最大利益の問題は、「値上がりした分だけを足し合わせる」という貪欲な発想で解決できます。コードも数行で書けるため、面接や競技プログラミングでも頻出の定番アルゴリズムとして覚えておくと役立ちます。