题目：410. 分割数组的最大值 - 力扣（LeetCode）

思路：对于这种最大值最小的问题，首先就可以先条件反射的想出：能不能用二分的思想去做（大部分这种题都是这样）。对于这道题可以知道如果不限制切割份数的话，那么最大的子串是所以元素放一起也就是所有元素的和num，最小就是全部都当成一份最大值是集合中的最大值a = max(nums)。所以二分的上限就是num，最小就是a。

确定好上限和下限后就可以进行二分了，这里的二分就是去找满足切割条件时的最大值，如果在框定的最大值里面需要切割的数量小于等于规定数量时，说明我们选择的值是可以成功将所有的子请区间包含的，这其中我们选择的值可能会大于或者等于所有区间的最大值，那么我们就可以将上限变为这个值。同理，如果我们选择的值如果让切割的区间数量大于了规定数量，就说明我们选择的数值偏小了，所以将下限提高为当前值加1(因为当前值也是不合理的所以才有的加一)；

具体代码：

typedef long long ll;
class Solution {
public:
    int splitArray(vector<int>& nums, int k) {
        //上下限
        ll l=0,r=0;
        for(int i=0;i<nums.size();i++){
            r+=(ll)nums[i];
            l=max(l ,(ll)nums[i]);
        }
        while(l<r){
            ll p = (l+r)/2ll;
            if(pp(nums,k,p)){
                r=p;
            }else{
                l=p+1ll;
            }
        }
        return l;
    }

    bool pp(vector<int>& nums,int k,ll x){
        ll num=0;
        //可分成的段数
        int cnt=1;
        for(int i=0;i<nums.size();i++){
            if((ll)nums[i]+num>x){
                cnt++;
                num=(ll)nums[i];
            }else{
                num+=(ll)nums[i];
            }
        }
        return cnt<=k;
    }
};

哈哈，还用一种更好理解这种题目的方法，可以将这个做法想成你在一个条状图里面，有者一段一段的线条，如果将所有线条拼在一起，那么这个线条的长度其实就是我们的上限，则它的份数就是1；将所有的线条摊开，那么最高的那个线段就是我们的下限，而它的份数就是线段的数量。将上限和下限向着中间靠拢，重叠时就是我们要求的值了。