410. 分割数组的最大值

410. 分割数组的最大值

给定一个非负整数数组和一个整数 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，在所有情况中最小。

解题思路

二分查找 动态规划

方法一 | 二分查找

二分查找的方法：
n个数，定义 res = 【分割数组的最大值】

• 如果分割成n组,那么res就是这n个数中的最大值
• 如果分割成1组，那么res这n个数的和

现在题目给定分割成m，则 1 <= m <= max(nums)
若分割的组数越小，res越大，极端情况就是m=1时res等于整个数组的和
所以m和res之间的关系是单调递减的
由上可知res的范围：max(nums) <= res <= sum(nums)
所以我们可以让res从这个范围从左到右取值测试，看哪个值是真正所求
从左到右遍历给定的数组nums，对这个数组进行分组
累加当前的和，若当前的和小于测试的res，继续累加，直到累加和大于res。
此时分组数cnt加一，并且累加和要从当前的数重新开始
遍历完数组我们将分组数cnt和m进行比较

• 若 cnt <= m ,那么说明res大了，我们要将res减小点
• 若 cnt > m,那么说明res小了，需要将res变大点

为了加速查找res,使用二分查找，而二分查找的范围就是 [ max(nums) , sum(nums)]

class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        int len = nums.size();
        long long left = 0,right = 0;
        for(int i=0;i<len;i++) {
            right += nums[i];
            left = nums[i] > left ? nums[i]:left;//初始时left为nums中的最大值
        }
        while(left < right) {
            long long  mid = left + ((right - left) >> 1); 
            long long sum = 0;
            int cnt = 1;
            //开始进行分组，相邻和不超过mid的最大值的这些数分为一组
            for(int i=0;i<len;i++) {
                if(sum + nums[i] > mid) {
                    cnt++;
                    sum = nums[i];//到一个分组了，sum重新开始新的一个分组
                }else{
                    sum += nums[i];//不断累加
                }
            }
            if(cnt <= m)  right = mid;
            else left = mid + 1;
        }
        return left;
    }
};