leetcode 410. 分割数组的最大值

深藏阁楼爱情的钟 2023-07-03 10:56 61阅读 0赞

思路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;
        }
    };