leetcode 410. 分割数组的最大值（二分巨水，但是还可以dp 利用单调性）

题目

无论二分还是dp,都需要题目保证非负整数。

dp[i][m]=sigma min(max(dp[j][m-1],sum[i]-sum[j])) 其中0<=j<i。
但是我们对于i，并不需要把[0,i)的所有j遍历一遍。
而是直接找出 最大的 j 满足 dp[j][m-1]<=sum[i]-sum[j]. 假设这个j最后求出来pos;
我们为什么直接找到pos就行了呢？pos对应的m个分组和的最大值是sum[i]-sum[pos]。

• 假如j<pos，那么dp[j][m-1]会更小，sum[i]-sum[j]会更大，m个分组和里面最大值就是 sum[i]-sum[j]了，大于pos对应的sum[i]-sum[j]，所以j<pos的都不能使答案更小
• 假如j>pos，那么dp[j][m-1]会更大, sum[i]-sum[j]会更小，m个分组和里面最大值是dp[j][m-1]（因为假如dp[j][m-1]<=sum[i]-sum[j]，那么pos就会是这个j，，）,又不能确定dp[j][m-1]和sum[i]-sum[pos]的大小，所以这个要更新下答案。
• j比pos+1还大时就不可能了。j>pos+1，最值一定是dp[j][m-1]，而dp[j][m-1]>=dp[j-1][m-1](也就是dp[ pos+1][m-1])，所以。。

其次就是求每个i对应的pos时，也是单调的。i1>i2则 pos1>=pos2;

时间复杂度： o(n*m)

class Solution {
public:
    int splitArray(vector<int>& nums, int M) {
        int n=nums.size(),*sum=new int[n],*dp=new int[n];
        sum[0]=dp[0]=nums[0];
        for(int i=1;i<n;++i) sum[i]=sum[i-1]+nums[i],dp[i]=sum[i];
        for(int m=2;m<=M;++m){
            int pos=n-1;
            for(int i=n-1;i>=1;--i){
                while(pos>=0&&dp[pos]>sum[i]-sum[pos]) --pos;
                if(pos!=-1) dp[i]=max(dp[pos],sum[i]-sum[pos]);
                if(pos!=n-1) dp[i]=min(dp[i],max(dp[pos+1],sum[i]-sum[pos+1]));
            }
        }
        return dp[n-1];
    }
};

二分最大值，也就是二分答案。

class Solution {
#define INF 0x3f3f3f3f
public:
    int cal(int mid,vector<int>& nums){
        int n=nums.size(),cnt=0;
        for(int i=0,j,sum;i<n;i=j){
            j=i,sum=0;
            while(j<n&&sum+nums[j]<=mid) sum+=nums[j++];
            ++cnt;
        }
        return cnt;
    }
    int splitArray(vector<int>& nums, int m) {
        int n=nums.size(),low=-INF,high=0,mid;
        for(int i=0;i<n;++i) low=max(low,nums[i]),high+=nums[i];
        while(low<=high){
            mid=(low+high)>>1;
            if(cal(mid,nums)<=m) high=mid-1;
            else low=mid+1;
        }
        return high+1;
    }
};