JavaScriptで配列を分割したときの平均値の合計の最大値を求める方法

問題の概要

数値の配列 arr を第一引数に、数値 num（num は arr の長さ以下）を第二引数に受け取るJavaScript関数を作成します。

この関数の目的は、配列 arr を最大 num 個の「隣接する空でないグループ」に分割することです。分割の際、どの要素も取り残してはいけません。

そして、考えられるすべての分割方法の中から、各グループの平均値の合計が最大になるような分割を選び出し、その最大の合計値を返します。

例として、次の入力を考えてみましょう。

入力

const arr = [10, 2, 3, 4, 10];
const num = 3;

出力

const output = 23;

出力の解説

配列を次のように分割した場合を考えます。

[10], [2, 3, 4], [10]

このとき、各グループの平均値の合計は次のように計算されます。

10 + (9) / 3 + 10 = 23

この 23 が、すべての分割方法の中で最大の合計値となります。

解法のアプローチ：動的計画法

この問題は、動的計画法（DP）を用いることで効率的に解くことができます。各インデックスの位置と残りの分割数を状態として管理し、各区切り位置で「ここでグループを区切る」か「区切らずに続ける」かを選択しながら、平均値の合計が最大になる組み合わせを探索していきます。

具体的には、二次元の行列（matrix）を用意し、配列の後ろの要素から順に計算を進めることで、各状態における最大値を段階的に求めます。

コード例

以下が実際のコードです。

const arr = [10, 2, 3, 4, 10];
const num = 3;
const greatestSum = (arr, num) => {
    const sum = (arr = []) => arr.reduce((acc, num) => acc + num, 0)
    let matrix = new Array(num + 1).fill(0).map(() => new Array(arr.length + 1).fill(0))
    for (let index = arr.length; index >= 0; index--) {
        const current = new Array(num + 1).fill(0).map(() => new Array(arr.length + 1).fill(0))
        for (let currentK = num; currentK >= 0; currentK--) {
            for (let count = arr.length - 1; count >= 0; count--) {

                if (index === arr.length && currentK === num) {
                    current[currentK][count] = 0
                } else if (index < arr.length && currentK < num) {
                    current[currentK][count] = Math.max(
                    matrix[currentK][count + 1], matrix[currentK + 1][0] + sum(arr.slice(index - count, index + 1)) / (count + 1) )
                } else {
                    current[currentK][count] = -Infinity
                }
            }
        }
        matrix = current
    }
    return matrix[0][0]
}
console.log(greatestSum(arr, num));

出力

23

このように動的計画法を活用することで、配列を最大 num 個のグループに分割したときの平均値の合計の最大値を、全探索よりも効率的に求めることができます。