leetcode410_分割数组的最大值详解程序员

410. 分割数组的最大值

Difficulty: 困难

给定一个非负整数数组和一个整数 m，你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。

注意:
数组长度 n 满足以下条件:

• 1 ≤ n ≤ 1000
• 1 ≤ m ≤ min(50, n)

示例:

输入: 
nums = [7,2,5,10,8] 
m = 2 
 
输出: 
18 
 
解释: 
一共有四种方法将nums分割为2个子数组。 
其中最好的方式是将其分为[7,2,5] 和 [10,8]， 
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。 

Solution

这里采用了二分法来解决问题。题目要求将数组分为m组，然后目的是要每一组的和尽可能近似，最后输出所有小组和的最大值（res）。为什么可以想到二分法？因为这里我们可以确定res的范围，他必定在[max(nums),sum(nums)]这一区间中。根据这一区间，就可以对每个值一一试探：

1. 取每个小组时，贪心地使小组和与mid最接近但不超过mid，保证mid是所有小组和的最大值（这里mid可能并不是其中某个小组的和，但没关系）；
2. 依照上述规则，假设取到了cnt个小组，若cnt>m，说明这个mid值设置小了，left=mid+1；否则，说明这个mid值满足条件，但是mid仍有可能更小，right=mid；
3. 最终left==right的时候，就必然是最终的各小组和的最大值，因为mid过小或者过大的情况都已经试过了。

下面是代码。

class Solution {
    
    public int splitArray(int[] nums, int m) {
    
        if(nums == null || nums.length == 0 || m == 0){
    
            return 0; 
        } 
        long left = nums[0], right = nums[0]; 
 
        //left为数组中的最大值，right为整个数组的和 
        for(int i=1; i<nums.length; i++){
    
            left = Math.max(left, nums[i]); 
            right += nums[i]; 
        } 
 
        while(left < right){
    
            long mid = (left + right) >> 1; 
            int sum = 0, cnt = 0; 
            for(int i : nums){
    
                if(sum + i > mid){
    
                    sum = i; 
                    cnt++; 
                }else{
    
                    sum += i; 
                } 
            } 
            //注意cnt这里是少算了最后一组的，要+1 
            cnt++; 
            if(cnt > m){
    
                left = mid + 1; 
            }else{
    
                right = mid; 
            } 
        } 
        return (int)right; 
    } 
}