C++で配列をm個に分割し、最大部分配列和を最小化するアルゴリズム

正の整数からなる配列と整数 m が与えられたとします。この配列を m 個の連続する部分配列に分割できるものとし、分割後の各部分配列の要素和の中で最大値が最小となるような分割方法を見つけるアルゴリズムを考案します。

例えば、配列が [7, 2, 4, 10, 9]、m = 2 の場合を考えてみましょう。[7, 2, 4] と [10, 9] の2つの部分配列に分割すると、それぞれの和は 13 と 19 になり、最大値は 19 となります。これがこの入力に対する最適な答えです。

解法のアプローチ:動的計画法(DP)

この問題(LeetCode 410「Split Array Largest Sum」としても知られています)は、動的計画法を使って効率的に解くことができます。ポイントは次の2つです。

• 累積和(sum):sum[i] を「先頭から i 番目の要素までの合計」と定義します。これにより、任意の連続区間の和を O(1) で計算できます(sum[end-1] − sum[start-1])。
• DP配列(dp):dp[i] を「インデックス i 以降を残りの分割回数で分割したときの、最大部分配列和の最小値」として更新していきます。

アルゴリズムの手順

1. 関数 splitArray() を定義し、配列 v と分割数 m を引数として受け取ります。
2. n := v のサイズ とします。
3. サイズ n の累積和配列 sum と DP配列 dp を用意します。
4. sum[0] := v[0] とし、i = 1 から n−1 まで sum[i] := sum[i−1] + v[i] を計算します。
5. 初期化として、dp[0] := sum[n−1]、dp[i] := sum[n−1] − sum[i−1](i ≥ 1)を設定します。これは「まだ一切分割していない状態」を表しています。
6. i = 1 から m−1 まで、分割回数を1ずつ増やしながら以下を繰り返します。
   • start = 0 から n−i−1 まで:
     • end = start+1 から n−i まで:
       • dp[start] := min(dp[start], max(開始位置が0なら sum[end−1]、そうでなければ sum[end−1] − sum[start−1]、および dp[end]))
7. 最終的に dp[0] を返します。

C++での実装例

以下のコードで、実際の実装を確認してみましょう。

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
    int splitArray(vector<int>& v, int m) {
        int n = v.size();
        vector<long long int> dp(n);
        vector<long long int> sum(n);
        sum[0] = v[0];
        for(int i = 1; i < n; i++) sum[i] = sum[i-1] + v[i];
        dp[0] = sum[n-1];
        for(int i = 1; i < n; i++){
            dp[i] = sum[n-1] - sum[i-1];
        }
        for(int i = 1; i < m; i++){
            for(int start = 0; start < n - i; start++){
                for(int end = start + 1; end <= n - i; end++){
                    dp[start] = min(dp[start], max((start == 0 ? sum[end-1] : sum[end-1] - sum[start-1]), dp[end]));
                }
            }
        }
        return dp[0];
    }
};
main(){
    Solution ob;
    vector<int> v = {7,2,4,10,9};
    cout << (ob.splitArray(v, 2));
}

入力

[7,2,4,10,9]
2

出力

19

計算量の分析

時間計算量:O(n² × m) ― 3重のループ構造によるものです。
空間計算量:O(n) ― dp 配列と sum 配列のために必要です。

補足:二分探索による別解

n や m が大きい場合は、「最大部分配列和が x 以下になるように m 個以下の部分配列に分割できるか」という判定問題を二分探索で解くアプローチ(O(n log S)、S は配列の総和)も有効です。DPよりも高速に動作するため、制約が厳しい場面ではこちらを選ぶとよいでしょう。