本文共 2024 字，大约阅读时间需要 6 分钟。

1. 题目

给定一个非负整数数组和一个整数 m，你需要将这个数组分成 m 个非空的连续子数组。

注意:数组长度 n 满足以下条件:1 ≤ n ≤ 10001 ≤ m ≤ min(50, n)示例:输入:nums = [7,2,5,10,8]m = 2输出:18解释:一共有四种方法将nums分割为2个子数组。其中最好的方式是将其分为[7,2,5] 和 [10,8]，因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/split-array-largest-sum

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

2.1 二分查找

类似题目：

class Solution {
   public:    int splitArray(vector
   
    & nums, int m) {
       	long long l = 0, r = 1e15, maxsum, ans;    	while(l <= r)    	{
       		maxsum = l+((r-l)>>1);    		if(canSplitM(nums, maxsum, m))    			r = maxsum-1, ans = maxsum;    		else    			l = maxsum+1;    	}    	return ans;    }    bool canSplitM(vector
    
     & nums, long long maxsum, int m)     {
       	int count = 0;    	long long sum = 0;    	for(int i = 0; i < nums.size(); ++i)    	{
       		if(sum+nums[i] <= maxsum)//和的最大值没有超过设定的maxsum    			sum += nums[i];    		else//超过了    		{
       			count++;    			sum = 0;    			i--;    		}    		if(count >= m)    			return false;    	}    	return true;    }};
    
   

0 ms 7 MB

2.2 DP

• dp[i][j] 表示前 i 个数，分成 j 组的最小的最大和的值
• 先预处理求出前缀和 sum
• $dp[i][j]=min(dp[i][j],max(dp[k][j-1],sum[i]-sum[k])),k\in [0,i]$

class Solution {
   public:    int splitArray(vector
   
    & nums, int m) {
           int n = nums.size(), i, j, k;        vector
    
      sum(n+1, 0);        for(i = 1; i <= n; ++i)            sum[i] = sum[i-1] + nums[i-1];        vector
     
      
       > dp(n+1, vector
       
        (m+1,1e15));        dp[0][0] = 0;        for(i = 1; i <= n; ++i)            for(j = 1; j <= min(i,m); ++j)                for(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];    }};
       
      
     
    
   

412 ms 8.2 MB

我的CSDN

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

转载地址：https://michael.blog.csdn.net/article/details/107573654 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！