410. Split Array Largest Sum

caige 發布于2019-08-19 10:45 / 2593人閱讀

摘要：題目鏈接枚舉所有可能的，找最小的那個，二分枚舉優化復雜度，因為數組不含負數，根據是否滿足條件可以二分結果。注意由于不含負數，并且，相當于一條遞增，一條遞減的線找交點，極端情況沒有交點結果出現在兩端，所以依然可以找。

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服務器內存

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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