【Python】売却後の待機期間ありで株売買の最大利益を求めるアルゴリズム

ある企業の株価が時系列順にリストで与えられたとき、その株の売買によって得られる最大の利益を求めることを考えます。ただし、以下の2つの制約があります。

• 必ず買ってから売る必要がある（先に売ることはできない）
• 売却した後は1日待たないと再度買えない（クールダウン期間が存在する）

例えば、入力が prices = [2, 6, 9, 4, 11] の場合、出力は 11 となります。これは「2で買い → 6で売る → 1日待つ → 4で買い直す → 11で売る」という取引を行うことで、合計利益 11 を達成できるためです。

解法のアプローチ：動的計画法（DP）

この問題は、状態を2つに分けて管理する動的計画法で効率的に解けます。

• b：株を保有している状態での最大利益
• s：株を売却した状態での最大利益

株価リストを一度走査しながら、これら2つの状態を更新していくのがポイントです。なお、売却翌日に買えない制約は「前日の b の値（temp）をもとに s を更新する」ことで自然に実現できます。

アルゴリズムの手順

• s := 0 で初期化する
• b := -infinity（負の無限大）で初期化する
• i を 0 から株価リストのサイズ未満まで繰り返す：
  • temp := b として現在の値を退避する
  • b := max(b, s - prices[i]) で保有状態を更新する
  • i が 0 以外の場合、s := max(s, temp + prices[i - 1]) で売却状態を更新する
• 最終的に max(s, b + 株価リストの末尾要素) を返す

実装例

class Solution:
    def solve(self, prices):
        s = 0
        b = float("-inf")
        for i in range(len(prices)):
            temp = b
            b = max(b, s - prices[i])
            if i:
                s = max(s, temp + prices[i - 1])
        return max(s, b + prices[-1])

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

入力

[2, 6, 9, 4, 11]

出力

11

計算量について

このアルゴリズムは株価リストを一度だけ走査するため、時間計算量は O(n)、使用する変数が定数個のみのため空間計算量は O(1) となり、非常に効率的です。株価データの件数が多くても高速に最大利益を算出できます。