leetcode-410 分割数组的最大值

题目描述：给定一个非负整数数组 nums 和一个整数 m ，你需要将这个数组分成 m 个非空的连续子数组。

设计一个算法使得这 m 个子数组各自和的最大值最小。

代码实现

class Solution {
    public int splitArray(int[] nums, int m) {
        int minSum = Integer.MIN_VALUE;
        int maxSum = 0;
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            if (nums[i] > minSum) {
                minSum = nums[i];
            }
            maxSum += nums[i];
        }

        int left = minSum;
        int right = maxSum + 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            int currentM = calculateM(nums, mid);
            if (currentM == m) {
                right = mid;
            } else if (currentM > m) {
                left = mid + 1;
            } else if (currentM < m) {
                right = mid;
            }
        }
        return left;
    }

    public int calculateM(int[] nums, int sum) {
        int i = 0;
        int tmpSum = sum;
        int m = 0;
        while (i < nums.length) {
            if (tmpSum >= nums[i]) {
                tmpSum -= nums[i];
                i++;
                if (i == nums.length) {
                    m++;
                }
            } else {
                tmpSum = sum;
                m++;
            }
        }
        return m;
    }
}