Java binary search all candidates


  • 0
    D
    public class Solution {
        public int splitArray(int[] nums, int m) {
            if (nums == null || nums.length == 0 || m < 1 || m > nums.length) {
                return 0;
            }
            int n = nums.length;
            long left = Long.MIN_VALUE;
            long right = 0;
            for (int num : nums) {
                left = Math.max(left, num);
                right += num;
            }
            while (left < right) {
                long mid = left + (right - left) / 2;
                if (acceptable(nums, n, mid, m)) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            return (int)right;
        }
    
        public boolean acceptable(int[] nums, int n, long limit, int m) {
            int leftIndex = 0;
            for (int i = 1; i <= m; i++) {
                Long sum = null;
                int j = leftIndex;
                for (; j <= n - 1 - (m - i); j++) {
                    if (sum == null) {
                        if (nums[j] > limit) {
                            return false;
                        } else {
                            sum = (long)nums[j];
                        }
                    } else {
                        if (sum + nums[j] > limit) {
                            break;
                        } else {
                            sum += nums[j];
                        }
                    }
                }
                leftIndex = j;
            }
            return leftIndex == n;
        }
    }
    

Log in to reply
 

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