Leetcode 410 分割数组的最大值

题目链接

题目描述

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

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，在所有情况中最小。

解 二分答案验证

就这就算困难难度就离谱。

这种题目正向做会比较麻烦，但可以反向思考，如果知道答案验证这个答案是否可行会比较简单(遍历数组，用 sumsubs表示当前子数组内值的和，numsubs表示已有子数组的数量，当sumsubs加上当前值超过了答案时，把当前值作为新的子数组，并将numsubs值+1。遍历结束后验证numsubs是否超过m。)

既然已知答案验证会比较简单，就可以直接找出答案的上下限然后二分来判断是否可行。这题上限是数组值的和，下限是数组中的最大值。

class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        long long sum=0,min=0;
        int nsize=nums.size();
        for(int i=0;i<nsize;i++)
        {
            sum+=nums[i];
            min=min<nums[i]?nums[i]:min;
        }
        while(min<sum)
        {
            long long mid=min+(sum-min)/2,sumsubs=0;
            int numsubs=1;
            for(int i=0;i<nsize;i++)
            {
                if(sumsubs+nums[i]>mid)
                {
                    sumsubs=nums[i];
                    numsubs++;
                }
                else sumsubs+=nums[i];
            }
            if(numsubs<=m)sum=mid;
            else min=mid+1;
        }
        return min;
    }
};