即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

LeetCode 410. Split Array Largest Sum

编程语言 VDUYI 14℃ 0评论
本文目录
[隐藏]

1.题目

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:


If n is the length of array, assume the following constraints are satisfied:

1 ≤ n ≤ 1000


1 ≤ m ≤ min(50, n)

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.


2.思路

这道题的思路是来源于网上的解答。很有难度的一道题,因为感觉一般不会想到要用二分来解答这种题目。题目是要将一个非负数组nums分割为m个非空的连续子数组,最终的结果要使得m个子数组的和中的最大值最小,即最小化分割数组最大和。

这道题目有两个边界的情况,是:


1)如果 m=1时,则分割数组就是这个数组,分割数组最大和就是整个数组元素的和,即返回数组元素和。


2)如果 m 等于数组元素个数,则分割后的数组就是数组中的每个元素,则分割数组最大和是数组中最大的元素,即返回数组最大值。

可以很容易就想到,对于其他的m值,返回值就在上面这两个极端的范围内。这个时候就可以用二分来在这个范围里找到当前情况的返回值了。

二分查找:


遍历数组,利用mid值将数组进行分割,使得分割后的子数组的和最大且小于mid的值。分割之后,比较分割的数组个数count和m值。如果count < m,说明mid偏大,使得子数组个数不足,令right = mid;如果count > m,说明mid偏小,令left = mid+1;当count = m时得到的不一定是最终答案,可以尝试继续降低mid,直到left>right。最后返回left即可。


3.代码

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]; //右边是数组元素之和
        }
        if(m == 1) 
            return right;
        if(m == nums.size())
            return left;

        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,long mid)
    {
        int cur = 0, count = 1;
        for(int i = 0;i< nums.size();i++)
        {
            cur += nums[i];
            //利用mid值分割数组,使得子数组之和最大且不大于mid
            if(cur > mid)
            {
                cur = nums[i];
                count ++;
                if(count > m)
                {
                    return false;
                }
            }
        }
        return true;
    }
};

转载请注明:CodingBlog » LeetCode 410. Split Array Largest Sum

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情