C++で解く「株式売買の最適タイミング IV」― 最大k回の取引で利益を最大化する方法

問題概要

i番目の要素がi日目の株価を表す配列が与えられたとします。このとき、最大k回までの取引で得られる利益の最大値を求めるアルゴリズムを設計します。

例えば、入力が [3,2,6,4,0,3]、k = 2 の場合、出力は 7 になります。
その理由は次の通りです。

• 2日目（価格 = 2）に買い、3日目（価格 = 6）に売る → 利益は 6 − 2 = 4
• 5日目（価格 = 0）に買い、6日目（価格 = 3）に売る → 利益は 3 − 0 = 3

合計すると 4 + 3 = 7 となり、これが最大利益です。

解法のアプローチ

この問題は、メモ化再帰（トップダウン型の動的計画法）を用いることで効率的に解けます。手順は以下の通りです。

• サイズ (N+5) × (N+5) × 2 の3次元配列 dp を定義する
• dp テーブルをすべて -1 で初期化するための pre() メソッドを定義する
• 引数に arr（株価配列）、i（現在の日付）、n（日数）、k（残り取引回数）、status（株を保有中かどうか）を受け取る solve() メソッドを定義する
• i が n と等しい場合：
  • status が非ゼロ（まだ株を保有している）なら -100000 を返す（無効な状態を表す大きな負の値）
  • それ以外は 0 を返す
• dp[i][k][status] が -1 以外（計算済み）であれば、その値を返す
• まず ans := solve(arr, i+1, n, k, status)（何もしない場合）とする
• status が非ゼロの場合（株を保有中）：ans := max(ans, solve(arr, i+1, n, k−1, !status) + arr[i])（株を売却）
• status がゼロの場合：k > 0 であれば ans := max(ans, solve(arr, i+1, n, k, !status) − arr[i])（株を購入）
• 最後に dp[i][k][status] := ans を返す

main メソッドでの処理

• pre() を呼び出して dp テーブルを初期化する
• k ≥ 株価配列のサイズ ÷ 2 の場合、取引回数の制限は実質的に無意味になります。この場合は、隣接する日々の上昇幅をすべて足し合わせた値が答えとなります：
  • ans := 0
  • i := 1 から prices.size()−1 までループし、prices[i] > prices[i−1] なら ans += prices[i] − prices[i−1]
  • ans を返す
• それ以外の場合は solve(prices, 0, prices.size(), k, 0) を返す

実装例

以下のC++コードで、実際の実装を確認できます。

#include <bits/stdc++.h>
using namespace std;
typedef int lli;
const lli N = 1000;
lli dp[N + 5][N + 5][2];
class Solution {
   public:
   void pre(){
      for(lli i =0;i<=N;i++){
         for(lli j = 0;j<=N;j++){
            dp[i][j][1]=-1;
            dp[i][j][0]=-1;
         }
      }
   }
   lli solve(vector<int> &arr, lli i,lli n,lli k, lli status){
      if(i == n){
         if(status)return -100000;
         return 0;
      }
      if(dp[i][k][status]!=-1)return dp[i][k][status];
      lli ans = solve(arr, i+1,n,k,status);
      if(status){
         ans = max(ans,solve(arr,i+1,n,k-1,!status)+ arr[i]) ;
      } else {
         if(k>0){
            ans = max(ans,(lli)solve(arr,i+1,n,k,!status)- arr[i]) ;
         }
      }
      return dp[i][k][status] = ans;
   }
   int maxProfit(int k, vector<int>& prices) {
      pre();
      if(k>=prices.size()/2){
         int ans = 0;
         for(int i = 1; i < prices.size(); i++){
            if(prices[i] > prices[i-1])ans += prices[i] - prices[i-1];
         }
         return ans;
      }
      return solve(prices,0,prices.size(),k,0);
   }
};
main(){
   Solution ob;
   vector<int> v = {3,2,6,4,0,3};
   cout << (ob.maxProfit(2, v));
}

入力

{ 3,2,6,4,0,3}

出力

7

計算量について

このアルゴリズムの時間計算量は O(n × k)、空間計算量も O(n × k) です。メモ化により同じ状態の再計算を避けるため、全探索（指数時間）に比べて大幅に高速化されています。また、k が日数の半分以上ある場合は貪欲法で一括処理することで、さらに効率的に答えを求められます。