题目

image.png

思路

  • 首先分析题意，可以得出结论，结果必定落在【max（nums）， sum（nums）】这个区间内，因为左端点对应
  • 每个单独的元素构成一个子数组，右端点对应所有元素构成一个子数组。
  • 然后可以利用二分查找法逐步缩小区间范围，当区间长度为1时，即找到了最终答案。
  • 每次二分查找就是先算一个mid值，这个mid就是代表当前猜测的答案，然后模拟一下划分子数组的过程，可以得到用这个mid值会一共得到的子区间数cnt，然后比较cnt和m的关系，来更新区间范围。

    代码

    1.   public int splitArray(int[] nums, int m) {
    2.       int left = 0, right = 0;
    3.       for (int num : nums) {
    4.           left = Math.max(left, num);
    5.           right += num;
    6.       }
    7.       while (left < right) {
    8.           int cnt = 1, sum = 0, mid = left + (right - left) / 2;
    9.           for (int num : nums) {
    10.               sum += num;
    11.               if (sum > mid) {
    12.                   cnt++;
    13.                   sum = num;
    14.               }
    15.           }
    16.           if (cnt > m) {
    17.               left = mid + 1;
    18.           } else {
    19.               right = mid;
    20.           }
    21.       }
    22.       return left;
    23.   }
    分割数组的最大值