JavaScript 中最大的子数组总和

Z时代
2024-01-10
分类：综合

问题

我们需要编写一个 JavaScript 函数，它接受一个非负整数数组 arr 作为第一个参数，一个整数 num (num < arr.length) 作为第二个参数。

我们函数的任务是将数组拆分为 num 个非空的连续子数组。应该以这样的方式拆分数组，以最小化这些 num 个子数组中的最大总和。然后我们的函数应该返回子数组中累积的最大和。

例如，如果函数的输入是 -

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

那么输出应该是 -

const output = 15;

输出说明

虽然有四种方法可以将原始数组拆分为子数组，但是如果我们将数组拆分为两组 [5, 1, 4] 和 [8, 7]，那么这两组将具有最小的和，并且这两组中较大的是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));