🙃410 split array largest sum

https://leetcode.com/problems/split-array-largest-sum/

class Solution {
    public int splitArray(int[] nums, int m) {
        // Find the sum of all elements and the maximum element
        int sum = 0;
        int maxElement = Integer.MIN_VALUE;
        for (int element : nums) {
            sum += element;
            maxElement = Math.max(maxElement, element);
        }
        
        // Define the left and right boundary of binary search
        int left = maxElement;
        int right = sum;
        int minimumLargestSplitSum = 0;
        while (left <= right) {
            // Find the mid value
            int maxSumAllowed = left + (right - left) / 2;
            
            // Find the minimum splits. If splitsRequired is less than
            // or equal to m move towards left i.e., smaller values
            // 因为需要的最少split数少于m，所以满足条件，可能还有更小的sum
            // 不需要有subarray精确等于maxSumAllowed，只需要小于等于它就行了，
            // binary search的好处就是可以loose condition，直到我们搜索到最优的
            if (minimumSubarraysRequired(nums, maxSumAllowed) <= m) {
                right = maxSumAllowed - 1;
                minimumLargestSplitSum = maxSumAllowed;
            } else {
                // Move towards right if splitsRequired is more than m
                left = maxSumAllowed + 1;
            }
        }
        
        return minimumLargestSplitSum;
    }
    
    private int minimumSubarraysRequired(int[] nums, int maxSumAllowed) {
        int currentSum = 0;
        int splitsRequired = 0;
        //最少的split数就是每个subarray都尽可能接近maxSumAllowed的时候
        for (int element : nums) {
            // Add element only if the sum doesn't exceed maxSumAllowed
            if (currentSum + element <= maxSumAllowed) {
                currentSum += element;
            } else {
                // If the element addition makes sum more than maxSumAllowed
                // Increment the splits required and reset sum
                currentSum = element;
                splitsRequired++;
            }
        }
        
        // Return the number of subarrays, which is the number of splits + 1
        return splitsRequired + 1;
    }
}

实在是不想写一遍了，记得把这道题重做一遍

class Solution {
    public int splitArray(int[] nums, int k) {
        int lo = 0;
        int hi = 0;
        for (int num : nums) {
            lo = Math.max(lo, num);
            hi += num;
        }
        //搜索区间是[lo, hi)，区间为空时是lo == hi，所以while(区间非空) <=> while(lo < hi)
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            //k是subarray的数量，split是k-1
            if (minSplitNeeded(nums, mid) <= k - 1) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return hi;
    }
    private int minSplitNeeded(int[] nums, int maxSum) {
        int curSum = 0;
        int split = 0;
        for (int num : nums) {
            if (curSum + num <= maxSum) {
                curSum += num;
            } else {
                curSum = num;
                split++;
            }
        }
        return split;
    }
}