410. Split Array Largest Sum

public int splitArray(int[] nums, int k) {
    int minMax = 0; // 最小的最大值，用于后续搜索的左边界
    int sum = 0;
    for (int num : nums) {
        minMax = Math.max(minMax, num); // 非空数组，即单个最大的元素值
        sum += num;
    }

    int left = minMax, right = sum; // [left, right], 注意 right 为 sum
    while (left < right) {
        int mid = (left + right) >>> 1;

        int count = splitBySum(nums, mid);
        if (count > k) {
            // 分出的个数大于 k 个，说明当前尝试的和太小了
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return left;
}

private int splitBySum(int[] nums, int sum) {
    int count = 1;
    int subSum = 0;

    for (int num : nums) {
        if (subSum + num > sum) {
            subSum = 0;
            count++;
        }
        subSum += num;
    }

    return count;
}

References

410. Split Array Largest Sum