leetcode 410. 分割数组的最大值-蒲公英云

leetcode 410. 分割数组的最大值

思路1：动态规划.这题有点特殊。之前做过一道划分m段的和的最大值。难道其实比这题要高。

dp[i][j]表示前i个数分成j段得到的最大值的最小值（第i个一定包含在第j段里面）。所以我们要做的就是去枚举第j段的开始即可。为了方便求出任一段的和，先预处理求一个前缀和。

dp[i][j]=min(dp[i][j],max(dp[k][j-1],sum[i]-sum[k])

class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        int n=nums.size();
        unsigned long long dp[n+2][m+2];
        memset(dp,127,sizeof(dp));
        unsigned long long sum[n+3];
        sum[0]=0;
        dp[0][0]=0;
        for(int i=1;i<=n;i++)
        {
            sum[i]=sum[i-1]+nums[i-1];
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                for(int k=0;k<i;k++)
                {
                    dp[i][j]=min(dp[i][j],max(dp[k][j-1],sum[i]-sum[k]));
                }
            }
        }
        return dp[n][m];
    }
};

思路2：对于最大值最小化的问题，二分往往是正解。二分的思路是猜需要的最大值最小到底是谁，它的范围一定在[max(num[i],sum{num[i]}] 之间。所以在这个区间二分即可。

二分思路：每次取mid=(l+r)>>1 .然后遍历数组，看能划分的不超过mid的数组有多少个。记为cnt。若cnt>m 也就是以mid为最大值划分出来的数组，数量过多。那么说明mid过小。反之，mid过大。

class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        int n=nums.size();
        long long l=0,r=0;
        for(int i=0;i<n;i++)
        {
            r+=nums[i];
            l=max(l,(long long)nums[i]);
        }
        while(l<r)
        {
            long long mid=(l+r)>>1;
            int cnt=1;
            long long tmp=0;
            for(int i=0;i<n;i++)
            {
                tmp+=nums[i];
                if(tmp>mid)
                {
                    tmp=nums[i];
                    cnt++;
                }
            }
            if(cnt>m)
            {
                l=mid+1;
            }
            else
            {
                r=mid;
            }
        }
        return l;
    }
};