首页 > 代码库 > [LeetCode] Split Array Largest Sum 分割数组的最大值

[LeetCode] 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 = 2Output:18Explanation: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]

 

class Solution {public:    int splitArray(vector<int>& nums, int m) {        long long left = 0, right = 0;        for (int i = 0; i < nums.size(); ++i) {            left = max((int)left, 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 left;    }    bool can_split(vector<int>& nums, int m, int sum) {        int 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;    }};

 

参考资料:

https://discuss.leetcode.com/topic/61314/binary-search-c-solution

 

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

[LeetCode] Split Array Largest Sum 分割数组的最大值