# LC410 - Split Array Largest Sum
## 线性关系 二分查找猜答案

class Solution {
    /*
    x: The sum of sub-array
    f(x): If the sum of sub-array is x, it can split f(x) sub-arrays.
    */
    public int splitArray(int[] nums, int m) {
        
        int length = nums.length;
        int minSum = 0; // the max element of array
        int maxSum = 0; // the sum of array
        
        for (int num : nums) {
            minSum = Math.max(minSum, num);
            maxSum += num;
        }
        
        while (minSum + 1 < maxSum) {
            int midSum = minSum + (maxSum - minSum) / 2;
            if (canSplitSubArrayBy(midSum, m, nums)) {
                maxSum = midSum;
            } else {
                minSum = midSum;
            }
        }
        
        // minimum
        if (canSplitSubArrayBy(minSum, m, nums)) {
            return minSum;
        }
        if (canSplitSubArrayBy(maxSum, m, nums)) {
            return maxSum;
        }
        return -1;
    }
    
    // inverse function
    private boolean canSplitSubArrayBy(int targetSum, int targetNumSubArray, int[] nums) {
        int length = nums.length;
        int numSubArray = 0;
        int sumSubArray = 0;
        
        for (int i = 0; i < length; i++) {
            sumSubArray += nums[i];
            if (sumSubArray == targetSum) {
                numSubArray++;
                sumSubArray = 0;
            } else if (sumSubArray > targetSum) {
                numSubArray++;
                sumSubArray = nums[i];
            }
        }
        if (sumSubArray != 0) {
            numSubArray++;
        }
        
        return numSubArray <= targetNumSubArray;
    }
}