C++で平均値の合計を最大化する方法｜動的計画法による解説

問題概要

数列 A を最大 K 個の隣接するグループに分割することを考えます。このとき、スコアは「各グループの平均値の合計」として定義されます。目的は、達成可能な最大のスコアを求めることです。

例として、A = [9, 1, 2, 3, 9]、K = 3 の場合を見てみましょう。最適な分割は [9]、[1, 2, 3]、[9] であり、このときのスコアは次のように計算できます。

9 + (1 + 2 + 3) / 3 + 9 = 20

一方、[9, 1]、[2]、[3, 9] のように分割すると、得られるスコアはこれより小さくなります。

解法のアプローチ：動的計画法（メモ化再帰）

この問題は、動的計画法（DP）とメモ化再帰を組み合わせることで効率的に解けます。「インデックス idx 以降の要素を、残り k 個のグループに分割したときの最大スコア」を状態として定義し、再帰的に計算していきます。

アルゴリズムの手順

• 二次元の DP テーブル dp を定義する
• 再帰関数 solve() を定義する（引数：配列 A、現在のインデックス、残りのグループ数 k）
• idx が配列 A のサイズ以上なら 0 を返す（すべての要素を使い切った状態）
• k が 0 なら -100000 を返す（グループ数が足りない不正な状態を表す）
• dp[idx][k] が -1 以外（計算済み）なら、その値を返して再計算を回避する
• ret を負の無限大、sum を 0 で初期化する
• i を idx から配列の末尾までループさせる
  • sum に A[i] を加算する
  • ret を「sum / (i − idx + 1) + solve(A, i + 1, k − 1)」と比較し、大きい方を採用する
• dp[idx][k] に ret を格納して返す

メイン関数での処理

• n を配列 A のサイズとする
• dp を n × (K + 1) のサイズで作成し、すべて -1 で初期化する
• solve(A, 0, K) の結果を返す

C++ による実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   vector < vector <double> > dp;
   double solve(vector <int>& A, int idx, int k){
      if(idx >= A.size()) return 0;
      if(!k) return -100000;
      if(dp[idx][k] != -1) return dp[idx][k];
      double ret = INT_MIN;
      double sum = 0;
      for(int i = idx; i < A.size(); i++){
         sum += A[i];
         ret = max(sum / (i - idx + 1) + solve(A, i + 1, k - 1), ret);
      }
      return dp[idx][k] = ret;
   }
   double largestSumOfAverages(vector<int>& A, int K) {
      int n = A.size();
      dp = vector < vector <double> > (n, vector <double>(K + 1, -1));
      return solve(A, 0, K);
   }
};
main(){
   vector<int> v = {9,1,2,3,9};
   Solution ob;
   cout << (ob.largestSumOfAverages(v, 3));
}

入力

[9,1,2,3,9]
3

出力

20

計算量の評価

状態の総数は n × K 個であり、各状態の計算に O(n) の時間がかかるため、時間計算量は O(n² × K) となります。また、DP テーブルの分だけメモリを必要とするため、空間計算量は O(n × K) です。メモ化によって同じ状態の再計算が不要になるため、単純な全探索と比べて大幅に高速化できるのがポイントです。