Pythonで株の売買を最大2回まで行った場合の最大利益を求めるプログラム

問題の概要

時系列順に並んだ企業の株価を表す数値リスト prices が与えられたとします。このとき、買いと売りを合わせて最大2回まで行えるという条件のもとで、得られる利益の最大値を求める必要があります。なお、取引は必ず「先に買って、後で売る」という順序で行わなければなりません。

例えば、入力が prices = [2, 6, 3, 4, 2, 9] の場合、出力は 11 になります。これは、最初に価格2で購入して6で売却し、その後再び価格2で購入して9で売却することで、(6−2) + (9−2) = 11 の利益を得られるためです。

解法のアプローチ

この問題は、4つの状態変数を使って動的に最適値を更新していくことで解けます。各状態は次の意味を持ちます。

• first_buy: 1回目の購入を行ったときの利益（負の値＝支出）の最大値
• first_sell: 1回目の売却を完了したときの利益の最大値
• second_buy: 2回目の購入を行ったときの累積利益の最大値
• second_sell: 2回目の売却を完了したときの累積利益の最大値

具体的な手順は以下の通りです。

• 初期値として first_buy := −∞、first_sell := −∞、second_buy := −∞、second_sell := −∞ を設定する
• prices 内の各価格 px に対して、以下を順に実行する
  • first_buy := max(first_buy, −px)
  • first_sell := max(first_sell, first_buy + px)
  • second_buy := max(second_buy, first_sell − px)
  • second_sell := max(second_sell, second_buy + px)
• 最後に、0、first_sell、second_sell の中から最大値を返す

この方法のポイントは、各価格を一度だけ走査すればよいため、計算量が O(n)、空間計算量も O(1) と非常に効率的である点です。また、1回しか取引しない場合や取引しない場合（利益0）にも自動的に対応できます。

実装例

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

class Solution:
    def solve(self, prices):
        first_buy = first_sell = float("-inf")
        second_buy = second_sell = float("-inf")
        for px in prices:
            first_buy = max(first_buy, -px)
            first_sell = max(first_sell, first_buy + px)
            second_buy = max(second_buy, first_sell - px)
            second_sell = max(second_sell, second_buy + px)
    return max(0, first_sell, second_sell)

ob = Solution()
prices = [2, 6, 3, 4, 2, 9]
print(ob.solve(prices))

入力

[2, 6, 3, 4, 2, 9]

出力

11

まとめ

このプログラムでは、4つの状態変数を価格リストの走査と同時に更新することで、最大2回の売買による最大利益を効率的に求めています。単純な全探索では O(n²) 以上かかる場面でも、この手法なら線形時間で処理できるため、実務的なデータサイズにも十分対応可能です。