JavaScriptで配列をnum個に分割!部分配列の最大合計を最小化する二分探索アルゴリズム

問題概要

負でない整数のみを含む配列 arr を第1引数に、整数 num(num < arr.length)を第2引数として受け取るJavaScript関数を作成します。

関数の目的は、元の配列を空でない連続した部分配列にちょうど num 個に分割することです。その際、各部分配列の合計値の中で最大のものが最小になるように分割し、その最小化された「最大合計」を戻り値として返します。

入力例

const arr = [5, 1, 4, 8, 7];
const num = 2;

出力例

const output = 15;

出力の解説

長さ5の配列を2つの部分配列に分割する方法は全部で4通りあります。それぞれの分割における最大合計を比べてみましょう。

• [5] と [1, 4, 8, 7] → 最大合計は 20
• [5, 1] と [4, 8, 7] → 最大合計は 19
• [5, 1, 4] と [8, 7] → 最大合計は 15
• [5, 1, 4, 8] と [7] → 最大合計は 18

最も最大合計が小さくなるのは [5, 1, 4](合計10)と [8, 7](合計15)に分割した場合で、このとき大きい方の 8 + 7 = 15 が答えとなります。

サンプルコード

const arr = [5, 1, 4, 8, 7];
const num = 2;

const splitArray = (arr = [], num = 1) => {
  let max = 0;
  let sum = 0;

  // 合計の上限がmidのとき、必要な部分配列の個数を返す
  const split = (arr, mid) => {
    let part = 1;
    let tempSum = 0;
    for (let num of arr) {
      if (tempSum + num > mid) {
        tempSum = num;
        part++;
      } else {
        tempSum += num;
      }
    }
    return part;
  };

  // 探索範囲:下限は配列内の最大要素、上限は合計値
  for (let num of arr) {
    max = Math.max(max, num);
    sum += num;
  }

  let low = max;
  let high = sum;
  while (low < high) {
    const mid = Math.floor((high + low) / 2);
    const part = split(arr, mid);
    if (part > num) {
      // 分割数が多すぎる → 上限を引き上げる
      low = mid + 1;
    } else {
      // 条件を満たす → さらに小さい上限を探す
      high = mid;
    }
  }
  return low;
};

console.log(splitArray(arr, num));

コードの解説：二分探索によるアプローチ

このコードでは二分探索(バイナリサーチ)を使って、最適な分割を効率的に見つけています。

1. 探索範囲の決定： 求める答え(最大合計)は、最小でも配列内の最大要素(max)以上、最大でも配列全体の合計(sum)以下に収まります。この [max, sum] の範囲を二分探索の対象とします。
2. 判定処理(split関数)： 中間値 mid を「1つの部分配列に許容できる合計の上限」とみなし、配列を先頭から順に貪欲法(greedy)で詰めていき、必要な部分配列の個数を数えます。
3. 範囲の絞り込み： 必要な個数が num より多ければ mid が小さすぎるため low = mid + 1 とし、num 以下で収まるなら条件を満たしているので high = mid として、さらに小さい答えがないか探索を続けます。
4. 終了： low === high となった時点の値が、求めるべき最小の「最大合計」です。

このアルゴリズムの計算量は O(n log S)(n は要素数、S は配列の合計値)です。考えられるすべての分割パターンを試す力任せなアプローチと比べて格段に高速であり、LeetCode 410「Split Array Largest Sum」のような競技プログラミングの定番問題でも広く使われるテクニックです。

実行結果

コンソールには次のように出力されます。

15