@@ -0,0 +1,2593 @@
+package com.freetymekiyan.algorithms.level.hard;%0A%0A/**%0A * Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty%0A * continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.%0A * %3Cp%3E%0A * Note:%0A * Given m satisfies the following constraint: 1 %E2%89%A4 m %E2%89%A4 length(nums) %E2%89%A4 14,000.%0A * %3Cp%3E%0A * Examples:%0A * %3Cp%3E%0A * Input:%0A * nums = %5B7,2,5,10,8%5D%0A * m = 2%0A * %3Cp%3E%0A * Output:%0A * 18%0A * %3Cp%3E%0A * Explanation:%0A * There are four ways to split nums into two subarrays.%0A * The best way is to split it into %5B7,2,5%5D and %5B10,8%5D,%0A * where the largest sum among the two subarrays is only 18.%0A * %3Cp%3E%0A * Company Tags: Baidu, Facebook%0A * Tags: Binary Search, Dynamic Programming%0A */%0Apublic class SplitArrayLargestSum %7B%0A%0A    /**%0A     * Binary Search.%0A     * The max of the result is the sum of all the input numbers.%0A     * The min of the result is the max num of the input numbers.%0A     * Given a result, validate it by checking whether it generates m cuts.%0A     * Given the 3 conditions above we can do a binary search.%0A     * Use long for range to avoid overflow since it's sum of array.%0A     */%0A    public int splitArray(int%5B%5D nums, int m) %7B%0A        // Find sum and max.%0A        long sum = 0; // May overflow.%0A        int max = 0;%0A        for (int n : nums) %7B%0A            sum += n;%0A            max = Math.max(max, n);%0A        %7D%0A        // Binary search the minimum sum limit.%0A        long lo = max;%0A        long hi = sum;%0A        while (lo %3C hi) %7B%0A            long mid = lo + (hi - lo) / 2;%0A            if (validate(nums, mid, m)) %7B%0A                hi = mid;%0A            %7D else %7B%0A                lo = mid + 1;%0A            %7D%0A        %7D%0A        return (int) lo; // Convert long to int.%0A    %7D%0A%0A    /**%0A     * Validate whether given the max exceeds m subarrays.%0A     * If it needs more than m, return false. Otherwise return true.%0A     * Use an integer sum for current subarray sum.%0A     * Use an integer count for the # of subarrays.%0A     * For each number n in nums:%0A     * %7C Update sum to sum + n.%0A     * %7C If sum %3E max:%0A     * %7C   sum = n%0A     * %7C   count++%0A     * %7C   If count %3E m, return false.%0A     * Return true.%0A     */%0A    private boolean validate(int%5B%5D nums, long max, int m) %7B%0A        int sum = 0;%0A        int count = 1; // IMPORTANT! Already have 1 array.%0A        for (int n : nums) %7B%0A            sum += n;%0A            if (sum %3E max) %7B%0A                sum = n;%0A                count++;%0A                if (count %3E m) %7B%0A                    return false;%0A                %7D%0A            %7D%0A        %7D%0A        return true;%0A    %7D%0A%0A%7D%0A

update split array largest sum