1.質問

💡 Given an array  nums  which consists of non-negative integers and an integer  m , you can split the array into  m  non-empty continuous subarrays.
Write an algorithm to minimize the largest sum among these  m  subarrays.

個の非負数の数字の配列numsが与えられ、数字mの場合numsはm個の非空の連続配列に分けられる.

配列がすべて分割されると、各配列の数の和のうち最大値が分割総数の中で最も小さい総和が求められる.

条件

1 <= nums.length <= 1000

0 <= nums[i] <= 10^6

1 <= m <= min(50, nums.length)

2.方法

m個の配列に分けて、それらをすべて分離し、各和を予め求め、mの数字に基づいて指数時間複雑度を有する.numsの長さが50以上であれば、最大50個の配列に分割することができ、すべてが文であると仮定すると、50個のfor文を記述する必要がある.
この問題をどのように処理すべきか初めて分からなかったので、Leetcode問題が提供する情報の関連グラフを開いて確認しました.
Array | Binary Search | Dynamic Programming | Greedyここでバイナリ検索キーワードを確認し,それをどのように使用するかをさらに考えた.

2-1)タイリングされていない場合に発生する可能性のあるプロトコルの最大値、最大値

我々の目標は,各配列の数字と中の最値を返すことであるため,各配列の最切り上げ,最値を基準に二進探索を行えば問題を解決できると考えられる.

ピーク:numsアレイで最大の

最低価格

:numsアレイ合計

仮定問題の条件はnums = [7,2,5,10,8]、m = 2である.そうすると、最高値は10、最高値は32です.
最高値の中で2でない理由は、mを考慮せずに各配列を分割すると、各配列の最大値は答えに戻るべきであり、2479142であれば2479142、2479142、2479142、2479142、2479142、2479142に分けられ、その中で考慮された値は10であるため、10は最高値であるべきである.
最終的に、最高値は、各配列に1つの要素しか残っていないことをすべて分割したときの最大値(m = 5)であり、最も高い値は、分割されていないときの最大値([7])である.

2-2)最高額・最低価格を基準としたバイナリ検索

最高価格10と最低価格32の中間価格21が答えになるかどうかと思います.
ここで、答えとして実行可能かどうかの基準は、配列を分割する際に、すべての配列値の和が21未満であれば可能であり、大きい場合は不可能であることを意味する.このとき,正確に和を求める必要はない.
中間値21が答えであれば、最高値を21|に変更し、不可能であれば、最高値を21+1に変更する.最高値に1だけ加算する理由は、21はもはや不可能な数字なので、1、21を加算することは可能な数字なので、最安値に変更します.
最高価格と最低価格が同じになるまで繰り返すと、その価格が答えになります.

2−3）配列がm個に分割された場合、配列の各和が21にならないことをどのように決定するか。

アレイをm個に分割した場合、アレイは空ではなく連続したアレイであるため、1個のforゲート([2])と決定できる.

const canSplitNums = (nums, max, m) => {
  let count = 1;
  let sum = 0;

  for (const num of nums) {
    sum += num;
    if (sum > max) {
      sum = num;
      count += 1;
    }

    if (count > m) {
      return false;
    }
  }

  return true;
}

配列の個数[5]を用いて配列された各要素の和[10].

2[8]配列を巡回し、m = nums.lengthに要素を追加します.

m = 1がO(n)(ここではパラメータ受信の最大値)より大きい場合、配列はもう1つに分割され(countを1つ追加)、sumの値は対応する要素に初期化される(nums).

このステップ

を繰り返し、配列数sumが条件sumより大きい場合、21|要素の全てを巡回し、countが条件sumより小さい場合、numを返す.

3.完全なコード

const canSplitNums = (nums, max, m) => {
  let count = 1;
  let sum = 0;

  for (const num of nums) {
    sum += num;
    if (sum > max) {
      sum = num;
      count += 1;
    }

    if (count > m) {
      return false;
    }
  }

  return true;
}

const splitArray = (nums, m) => {
  let left = Math.max(...nums);
  let right = nums.reduce((acc, cur) => acc + cur);
  let mid = 0;

  while (left < right) {
    mid = Math.floor((left + right) / 2);

    if (canSplitNums(nums, mid, m)) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }

  return left;
};

は、左

の値を返します.クエリー条件は左<右、最終的には左==右が成立し、右の値を返します.