410. Split Array Largest Sum

caige 发布于2019-08-19 10:45 / 2568人阅读

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

410. Split Array Largest Sum

题目链接：https://leetcode.com/problems...

枚举所有可能的largest sum，找最小的那个，二分枚举优化复杂度，因为数组不含负数，根据largest sum是否满足条件可以二分结果。largest sum的范围是(sum(nums)/m, sum(nums))，找当前largest sum是否存在，判断存在的标准是：扫一遍array，看实现每个subarray的sum都<=当前largest sum的时候subarray的数量是否小于等于mm，注意求数组sum要用long，防止溢出。

public class Solution {
    public int splitArray(int[] nums, int m) {
        long sum = 0;
        for(int num : nums) sum += num;
        // binary search, find the minimum valid sum
        long l = sum / m;
        long r = sum;
        while(l < r) {
            long mid = l + (r - l) / 2;
            boolean valid = isValidSplit(nums, m, mid);
            if(valid) r = mid;
            else l = mid + 1;
        }
        
        return (int) l;
    }
    
    private boolean isValidSplit(int[] nums, int m, long sum) {
        int i = 0, n = nums.length;
        // count the minimum number of split
        int count = 0;
        // prev sum
        long prev = 0;
        // loop invariant: prev = 0, count = minimum splits so far
        while(i < n) {
            if(nums[i] > sum) return false;
            while(i < n && prev + nums[i] <= sum) {
                prev += nums[i++];
            }
            count++;
            if(count > m) return false;
            prev = 0;
        }
        
        return count <= m;
    }
}

还有一种dp的做法：
https://discuss.leetcode.com/...

dp的subproblem是：
dp[i][j]: split nums[0:i] into j parts,
dp的方程是：
dp[i][j] = min{ max{dp[k][j-1], sum(nums[k+1:i+1])} },
每个subproblem都遍历一遍可能的k，选择出最小的结果。注意由于array不含负数，dp[k-1] <= dp[k] 并且sum(nums[k:i+1]) >= sum(nums[k+1:i+1])，相当于一条递增，一条递减的线找交点，极端情况没有交点结果出现在两端，所以依然可以binary search找dp[k] == sum(nums[k+1:i+1])。

GPU云服务器云服务器 Largest 服务器r410 t410服务器内存 r410服务器内存

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

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

leetcode410. Split Array Largest Sum

摘要：在这里，边界被设置为该数组中可以得到的子数组元素和的最小值和最大值。在确定了数组元素和的上界和下界之后，就需要找出一种方法，来不断压缩区间直到最后一种。可以使用中间位置作为数组元素和的边界，即假设所有的连续数组的和都不会超过值。题目要求 Given an array which consists of non-negative integers and an integer m, y...

Jonathan Shieber 2019-08-16 17:31 评论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