Binary Search with Java using max value and sum of this array


  • 0
    R

    public int splitArray(int[] nums, int m) {
    // binary search or DP
    // the result must locate between maximum value of this array and sum of all numbers in this array
    if (nums == null || nums.length == 0) return 0;
    int sum = 0;
    int max = Integer.MIN_VALUE;
    for (int num : nums) {
    sum += num;
    max = Math.max(max, num);
    }

        // binary search
        int left = max;
        int right = sum;
        while (left <= right) {
            int middle = left + (right - left) / 2;
            if (canSplit(nums, m, middle)) {
                right = middle - 1; // selected mid is too large
            } else {
                left = middle + 1; // selected mid is too small
            }
        }
        return left;
    }
    public boolean canSplit(int[] nums, int m, int mid) {
        int cnt = 1;  // initial value must be one
        int total = 0;
        for (int num : nums) {
            total += num;
            if (total > mid) {
                total = num;
                cnt++;
                if (cnt > m) return false; // after cnt plus + 1 then continue check whether count more than m
            }
            
        }
        return true;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.