JAVA 6ms


  • 0
    C
    public class Solution {
        public int splitArray(int[] nums, int m) {
            int[] sums = new int[nums.length];
            int max = Integer.MIN_VALUE;
            for (int i = 0; i < sums.length; ++i){
                sums[i] = i == 0 ? nums[i] : sums[i-1] + nums[i];
                max = Math.max(max, nums[i]);
            }
            if (m == 1){
                return sums[nums.length - 1];
            }
            
            int left = max;
            int right = sums[nums.length - 1];
            int mid = 0;
            while(left < right){
                mid = left + (right - left)/2;
                if (isValid(sums, mid, m)){
                    right = mid;
                }else{
                    left = mid + 1;
                }
            }
            return left;
        }
        
        private int search(int[] sums, int start, int end, int target){
            while(start < end){
                int mid = start + (end - start + 1)/2;
                if (sums[mid] <= target){
                    start = mid;
                }else{
                    end = mid - 1;
                }
            }
            return start;
        }
        
        private boolean isValid(int[] sums, int target, int m){
            int start = 0;
            int end = 0;
            int subarrays = 0;
            int sum = 0;
            while(start < sums.length){
                end = search(sums, start, sums.length - 1, sum + target);
                sum = sums[end];
                if (++subarrays > m){
                    return false;
                }
                start = end + 1;
            }
            return true;
        }
    }
    

Log in to reply
 

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