JavaScriptのサブ配列の最大の合計

問題

最初の引数として非負の整数の配列arrを取り、2番目の引数として整数num（num

この関数のタスクは、配列をnum個の空でない連続サブ配列に分割することです。配列は、これらのnum個のサブ配列の中で最大の合計が最小になるように分割する必要があります。次に、関数はサブアレイ間で累積された最大の合計を返す必要があります。

たとえば、関数への入力が-

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

その場合、出力は-

const output = 15;

出力の説明

元の配列をサブ配列に分割する方法は4つありますが、配列を2つのグループ[5、1、4]と[8、7]に分割すると、これら2つのグループの合計は最小になり、これら2つのグループの大きい方が8 + 7=15これは関数が返す必要があります。

例

このためのコードは-

const arr = [5, 1, 4, 8, 7];
const num = 2;
const splitArray = (arr = [], num = 1) => {
   let max = 0;
   let sum = 0;
   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) {
      let mid = Math.floor((high+low)/2);
      let part = split(arr, mid);
      if (part > num) {
         low = mid + 1;
      } else {
         high = mid;
      }
   }
   return low;
};
console.log(splitArray(arr, num));

コードの説明：

ここでは、バイナリ検索を使用して、最適な分割を見つけることができるかどうかを確認しました。

出力

コンソールの出力は-

15