成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

410. Split Array Largest Sum

caige / 2608人閱讀

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

410. Split Array Largest Sum

題目鏈接：https://leetcode.com/problems...

枚舉所有可能的largest sum，找最小的那個，二分枚舉優(yōu)化復(fù)雜度，因為數(shù)組不含負(fù)數(shù)，根據(jù)largest sum是否滿足條件可以二分結(jié)果。largest sum的范圍是(sum(nums)/m, sum(nums))，找當(dāng)前l(fā)argest sum是否存在，判斷存在的標(biāo)準(zhǔn)是：掃一遍array，看實現(xiàn)每個subarray的sum都<=當(dāng)前l(fā)argest sum的時候subarray的數(shù)量是否小于等于mm，注意求數(shù)組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，選擇出最小的結(jié)果。注意由于array不含負(fù)數(shù)，dp[k-1] <= dp[k] 并且sum(nums[k:i+1]) >= sum(nums[k+1:i+1])，相當(dāng)于一條遞增，一條遞減的線找交點，極端情況沒有交點結(jié)果出現(xiàn)在兩端，所以依然可以binary search找dp[k] == sum(nums[k+1:i+1])。

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/76393.html

相關(guān)文章

  • leetcode410. Split Array Largest Sum

    摘要：在這里，邊界被設(shè)置為該數(shù)組中可以得到的子數(shù)組元素和的最小值和最大值。在確定了數(shù)組元素和的上界和下界之后，就需要找出一種方法，來不斷壓縮區(qū)間直到最后一種。可以使用中間位置作為數(shù)組元素和的邊界，即假設(shè)所有的連續(xù)數(shù)組的和都不會超過值。 題目要求 Given an array which consists of non-negative integers and an integer m, y...

    Jonathan Shieber 評論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 評論0 收藏0

  • [Leetcode] Maximum Subarray 子序列最大和

    摘要：最新更新請見原題鏈接動態(tài)規(guī)劃復(fù)雜度時間空間思路這是一道非常典型的動態(tài)規(guī)劃題，為了求整個字符串最大的子序列和，我們將先求較小的字符串的最大子序列和。而最大子序列和的算法和上個解法還是一樣的。 Maximum Subarray 最新更新請見：https://yanjia.me/zh/2019/02/... Find the contiguous subarray within an ar...

    summerpxy 評論0 收藏0

  • leetcode_53 Maximum Subarray

    摘要：如果單開元素加和更大判斷前面的子數(shù)組和是不是小于。此元素就成為了子數(shù)組的第一個元素。每次操作都要判斷，當(dāng)前是否是最大值，更新值。 題目詳情 Find the contiguous subarray within an array (containing at least one number) which has the largest sum.For example, given t...

    y1chuan 評論0 收藏0

  • leetcode53 Maximum Subarray 最大連續(xù)子數(shù)組

    摘要：我們可以分別得出這三種情況下的最大子數(shù)列和，并比較得出最大的那個。我們只需要考慮左子列的最大和以及跨越了左右的中子列的最大值。 題目要求 Find the contiguous subarray within an array (containing at least one number) which has the largest sum. For example, given ...

    Bamboy 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<