410. Split Array Largest Sum

 

Given an array which consists of non-negative integers and an integer  m , you can split the array into  m  non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these  m  subarrays.

Note:
Given  m  satisfies the following constraint: 1 ≤ m ≤ length(nums) ≤ 14,000.

Examples:

Input:
nums = [7,2,5,10,8]
m = 2

Output:
18

Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.

 

这道题给了我们一个非负数的数组 nums 和一个整数m,让把数组分割成m个非空的连续子数组,让最小化m个子数组中的最大值。开始以为要用博弈论中的最小最大化算法,可是想了半天发现并不会做,于是后面决定采用无脑暴力破解,在 nums 中取出所有的m个子数组的情况都找一遍最大值,为了加快求子数组和的运算,还建立了累计和数组,可以还是 TLE 了,所以博主就没有办法了,只能上网参考大神们的解法,发现大家普遍使用了二分搜索法来做,感觉特别巧妙,原来二分搜索法还能这么用,厉害了我的哥。首先来分析,如果m和数组 nums 的个数相等,那么每个数组都是一个子数组,所以返回 nums 中最大的数字即可,如果m为1,那么整个 nums 数组就是一个子数组,返回 nums 所有数字之和,所以对于其他有效的m值,返回的值必定在上面两个值之间,所以可以用二分搜索法来做。用一个例子来分析,nums = [1, 2, 3, 4, 5], m = 3,将 left 设为数组中的最大值5,right 设为数字之和 15,然后算出中间数为 10,接下来要做的是找出和最大且小于等于 10 的子数组的个数,[1, 2, 3, 4], [5],可以看到无法分为3组,说明 mid 偏大,所以让 right=mid,然后再次进行二分查找,算出 mid=7,再次找出和最大且小于等于7的子数组的个数,[1,2,3], [4], [5],成功的找出了三组,说明 mid 还可以进一步降低,让 right=mid,再次进行二分查找,算出 mid=6,再次找出和最大且小于等于6的子数组的个数,[1,2,3], [4], [5],成功的找出了三组,尝试着继续降低 mid,让 right=mid,再次进行二分查找,算出 mid=5,再次找出和最大且小于等于5的子数组的个数,[1,2], [3], [4], [5],发现有4组,此时的 mid 太小了,应该增大 mid,让 left=mid+1,此时 left=6,right=6,循环退出了,返回 right 即可,参见代码如下:

 

解法一:

class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        long left = 0, right = 0;
        for (int i = 0; i < nums.size(); ++i) {
            left = max(left, (long)nums[i]);
            right += nums[i];
        }
        while (left < right) {
            long long mid = left + (right - left) / 2;
            if (can_split(nums, m, mid)) right = mid;
            else left = mid + 1;
        }
        return right;
    }
    bool can_split(vector<int>& nums, long m, long sum) {
        long cnt = 1, curSum = 0;
        for (int i = 0; i < nums.size(); ++i) {
            curSum += nums[i];
            if (curSum > sum) {
                curSum = nums[i];
                ++cnt;
                if (cnt > m) return false;
            }
        }
        return true;
    }
};

 

上面的解法相对来说比较难想,在热心网友 perthblank 的提醒下,再来看一种 DP 的解法,相对来说,这种方法应该更容易理解一些。建立一个二维数组 dp,其中 dp[i][j] 表示将数组中前j个数字分成i组所能得到的最小的各个子数组中最大值,初始化为整型最大值,如果无法分为i组,那么还是保持为整型最大值。为了能快速的算出子数组之和,还是要建立累计和数组,难点就是在于推导状态转移方程了。来分析一下,如果前j个数字要分成i组,那么i的范围是什么,由于只有j个数字,如果每个数字都是单独的一组,那么最多有j组;如果将整个数组看为一个整体,那么最少有1组,所以i的范围是[1, j],所以要遍历这中间所有的情况,假如中间任意一个位置k,dp[i-1][k] 表示数组中前k个数字分成 i-1 组所能得到的最小的各个子数组中最大值,而 sums[j]-sums[k] 就是后面的数字之和,取二者之间的较大值,然后和 dp[i][j] 原有值进行对比,更新 dp[i][j] 为二者之中的较小值,这样k在 [1, j] 的范围内扫过一遍,dp[i][j] 就能更新到最小值,最终返回 dp[m][n] 即可,博主认为这道题所用的思想应该是之前那道题 Reverse Pairs 中解法二中总结的分割重现关系 (Partition Recurrence Relation),由此看来很多问题的本质都是一样,但是披上华丽的外衣,难免会让人有些眼花缭乱了,参见代码如下:

 

解法二:

class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        int n = nums.size();
        vector<long> sums(n + 1);
        vector<vector<long>> dp(m + 1, vector<long>(n + 1, LONG_MAX));
        dp[0][0] = 0;
        for (int i = 1; i <= n; ++i) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                for (int k = i - 1; k < j; ++k) {
                    long val = max(dp[i - 1][k], sums[j] - sums[k]);
                    dp[i][j] = min(dp[i][j], val);
                }
            }
        }
        return dp[m][n];
    }
};

 

Github 同步地址:

https://github.com/grandyang/leetcode/issues/410

 

类似题目:

Reverse Pairs

 

参考资料:

https://leetcode.com/problems/split-array-largest-sum/

https://leetcode.com/problems/split-array-largest-sum/discuss/89816/DP-Java

https://leetcode.com/problems/split-array-largest-sum/discuss/89873/binary-search-c-solution

https://leetcode.com/problems/split-array-largest-sum/discuss/89817/Clear-Explanation%3A-8ms-Binary-Search-Java

 

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation