C++で解く!クールダウン付き株式売買の最大利益を求めるアルゴリズム

この記事では、クールダウン期間ありの株式売買問題(Best Time to Buy and Sell Stock with Cooldown)をC++で解く方法を、動的計画法(DP)の考え方とともに分かりやすく解説します。

問題の概要

ある配列が与えられ、その i 番目の要素は i 日目の株価を表しているとします。このとき、利益が最大になるように売買を行うアルゴリズムを設計します。取引の回数に制限はなく、何度でも「買って売る」を繰り返せますが、次のルールを守る必要があります。

• 同時に複数の取引は行えない。つまり、新しい株を買う前に、必ず保有している株を売却しておかなければならない。
• 株を売却した翌日は株を購入できない(1日間のクールダウンが必要)。

例えば、入力が [1,2,3,0,2] の場合、出力は 3 になります。最適な操作の流れは「買い → 売り → クールダウン → 買い → 売り」です。

解法のポイント:2つの状態でDPを組む

この問題を効率的に解く鍵は、各日ごとの「状態」を明確に分けることです。ここでは次の2つの状態を管理します。

• endWithBuy:その日の時点で株を保有している状態での最大利益
• endWithSell:その日の時点で株を売却済み(非保有)の状態での最大利益

さらに、クールダウンのルールを正しく反映させるために、直前の状態を保存する prevBuy(前日の endWithBuy)と prevSell(前々日の endWithSell)という2つの変数を使います。これにより、「売却した翌日は買えない」という制約が自然に組み込まれます。

アルゴリズムの手順

• 初期化:endWithSell = 0、endWithBuy = 負の無限大(INT_MIN)、prevBuy = 0、prevSell = 0
• i = 0 から配列の末尾まで、以下を繰り返す。
  • prevBuy ← endWithBuy(前日の「保有状態」を退避)
  • endWithBuy ← max(endWithBuy, prevSell − Arr[i])(株を持ち続けるか、クールダウン明けに新しく買うか)
  • prevSell ← endWithSell(前日の「売却済み状態」を退避)
  • endWithSell ← max(endWithSell, prevBuy + Arr[i])(売らずにいるか、保有株を売るか)
• 最終的な endWithSell を答えとして返す

ポイントは、endWithBuy の更新に使う prevSell が「2日前時点の売却済み利益」になっている点です。これにより、売却翌日の購入が自動的に禁止され、クールダウンの要件が満たされます。

C++実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int maxProfit(vector<int>& p) {
      int endWithSell = 0;
      int endWithBuy = INT_MIN;
      int prevBuy =0, prevSell = 0;
      for(int i =0;i<p.size();i++){
         prevBuy = endWithBuy;
         endWithBuy = max(endWithBuy,prevSell - p[i]);
         prevSell = endWithSell;
         endWithSell = max(endWithSell, prevBuy + p[i]);
      }
      return endWithSell;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,3,0,2};
   cout << (ob.maxProfit(v));
}

入力

[1,2,3,0,2]

出力

3

計算量

• 時間計算量:O(n) — 配列を一度走査するだけです。
• 空間計算量:O(1) — 定数個の変数だけで状態を管理できます。

まとめ

クールダウン付きの株式売買問題は、「株を保有している」「売却済み」という2つの状態と、その遷移を丁寧に定義することが重要です。直前の状態を一時保存するテクニックにより、O(n)時間・O(1)空間という非常に効率的な解法が実現できます。LeetCode 309 などの典型問題として、DPの状態遷移設計を学ぶのに最適な題材です。