leetcode410. Split Array Largest Sum

Jonathan Shieber 发布于2019-08-16 17:31 / 816人阅读

摘要：在这里，边界被设置为该数组中可以得到的子数组元素和的最小值和最大值。在确定了数组元素和的上界和下界之后，就需要找出一种方法，来不断压缩区间直到最后一种。可以使用中间位置作为数组元素和的边界，即假设所有的连续数组的和都不会超过值。

题目要求

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.

将一个长度为n的正整数数组分割为m个非空的连续子数组，并分别计算每个子数组中所有元素的和。求一种分割方式，使得该分割方式生成的最大子数组和为所有分割方式中最小的。

比如题目中的例子nums = [7,2,5,10,8]，m = 2
一共有四种分割方式：

[7], [2,5,10,8]

[7,2], [5,8,10]

[7,2,5], [8,10]

[7,2,5,8], [10]

其中第三种分割得到的最大子数组的和是所有分割中最小的

思路一：动态规划

首先，我们可以通过递归的方式来遍历所有的分割方式，从而找到所有分割方式中最符合要求的那一种结果。代码如下：

    public int splitArray(int[] nums, int m) {
        //计算[0...i]中所有元素的和
        int[] sums = new int[nums.length+1];
        for(int i = 1 ; i<=nums.length ; i++) {
            sums[i] = nums[i-1] + sums[i-1];
        }
        return splitArray(nums, m, 0, sums);
    }
    
    //计算从cur位置开始，将其分割为m个子数组的最小分割场景
    public int splitArray(int[] nums, int m, int cur, int[] sums) {
        if(m == 1) {
            return sums[nums.length] - sums[cur];
        }
        int min = Integer.MAX_VALUE;
        int diff = Integer.MAX_VALUE;
        for(int i = cur+1 ; i<=nums.length-m+1 ; i++) {
            //当前元素为止，左边的子数组的元素和
            int left = sums[i]-sums[cur];
            //对右边的剩余元素递归的调用splitArray方法
            int right = splitArray(nums, m-1, i, sums);
            //如果出现二者之间的差递增的情况，则说明距离最优分割越来越远，则停止继续尝试
            if(diff < Math.abs(left - right)) {
                break;
            }
            diff = Math.abs(left - right);
            min = Math.min(min, Math.max(left, right));
        }
        return min;
    }

这种方法在大数据量的场景下会出现超时的问题，本质在于我们没有足够的复用中间的所有场景，如对于[i-j]这个子数组的k次分割的最优结果。如果我们记录从i到数组结尾进行k次分割的最优结果，该结果记录为dp[i][k]，则从j到数组结尾进行k+1次分割的最优结果为min(max(num(j), dp[j+1][k]), max(nums(j)+num(j+1), dp[j+2][k])... )
代码如下：

    public int splitArray(int[] nums, int m)
    {
        int L = nums.length;
        //记录0-i的元素和
        int[] S = new int[L+1];
        S[0]=0;
        for(int i=0; i
思路二：二分法
这是一个非常难想到的方法。二分法的难点一直在于如何划分初始边界，以及如何逐渐缩小边界并且确保左右指针可以相遇。在这里，边界被设置为该数组中可以得到的子数组元素和的最小值和最大值。
根据基本常识可知，数组的最大元素决定了该数组分割出的子数组的元素和的下界，而数组的元素和上界一定不会超过数组所有元素的和。
在确定了数组元素和的上界和下界之后， 就需要找出一种方法，来不断压缩区间直到最后一种。
可以使用中间位置作为数组元素和的边界，即假设所有的连续数组的和都不会超过mid值。假如按照这种方式得到的分割结果大于了规定的m个，则说明mid值作为最大元素和上界并不能够做到只分割出m个子数组，因此最大元素和上界一定在mid和有界中间。同理，假如按照这种方式得到的分割结果小于等于规定的m个，则说明mid值作为最大元素和上界能够满足分割出m个子数组，但是可能还存在更优解。通过这种二分法思路得到的最后结果就是所需要的最小分割结果。
    public int splitArray2(int[] nums, int m) {
        long sum = 0;
        int max = Integer.MIN_VALUE;
        for(int i = 0 ; i target) {
                sum = nums[i];
                count++;
                if(count > m) {
                    return false;
                }
            }
        }
        return true;
    }

云服务器 GPU云服务器 Largest Leetcod LeetCode 服务器r410

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/74552.html

410. Split Array Largest Sum

摘要：题目链接枚举所有可能的，找最小的那个，二分枚举优化复杂度，因为数组不含负数，根据是否满足条件可以二分结果。注意由于不含负数，并且，相当于一条递增，一条递减的线找交点，极端情况没有交点结果出现在两端，所以依然可以找。 410. Split Array Largest Sum 题目链接：https://leetcode.com/problems... 枚举所有可能的largest sum，...

caige 2019-08-19 10:45 评论0 收藏0
[LeetCode] Maximum Subarray

Problem Find the contiguous subarray within an array (containing at least one number) which has the largest sum. Example For example, given the array [-2,1,-3,4,-1,2,1,-5,4],the contiguous subarray [4...

Donald 2019-08-15 13:40 评论0 收藏0
[Leetcode] Maximum Subarray 子序列最大和

摘要：最新更新请见原题链接动态规划复杂度时间空间思路这是一道非常典型的动态规划题，为了求整个字符串最大的子序列和，我们将先求较小的字符串的最大子序列和。而最大子序列和的算法和上个解法还是一样的。 Maximum Subarray 最新更新请见：https://yanjia.me/zh/2019/02/... Find the contiguous subarray within an ar...

summerpxy 2019-08-14 16:11 评论0 收藏0
leetcode_53 Maximum Subarray

摘要：如果单开元素加和更大判断前面的子数组和是不是小于。此元素就成为了子数组的第一个元素。每次操作都要判断，当前是否是最大值，更新值。题目详情 Find the contiguous subarray within an array (containing at least one number) which has the largest sum.For example, given t...

y1chuan 2019-08-15 13:37 评论0 收藏0
leetcode53 Maximum Subarray 最大连续子数组

摘要：我们可以分别得出这三种情况下的最大子数列和，并比较得出最大的那个。我们只需要考虑左子列的最大和以及跨越了左右的中子列的最大值。题目要求 Find the contiguous subarray within an array (containing at least one number) which has the largest sum. For example, given ...

Bamboy 2019-08-14 18:08 评论0 收藏0