410. Split Array Largest Sum - Streak 17

이분탐색 문제이다.
너무 이분탐색이라 설명을 건너뛰고 주석으로 설명한다.

class Solution {
    public int splitArray(int[] nums, int k) {
        int lo = 0;
        for(int i = 0; i<nums.length; i++) lo = Math.max(lo, nums[i]);
        int hi = Integer.MAX_VALUE / 2;
        while(lo<=hi){
            int mid = (lo + hi)/2;
            if(check(nums, k, mid)){
                hi = mid - 1;
            }else{
                lo = mid + 1;
            }
        }
        return lo;
    }
    private boolean check(int[] nums, int k, int upperbound){
        int now = 0;
        int nowSubArrCnt = 0;
        for(int i = 0; i<nums.length; i++){
            // 부분배열의 합이 upperbound보다 커지면 끊기
            if(now + nums[i] > upperbound){
                now = 0;
                nowSubArrCnt++;
                // 배열의 수가 k개보다 많아지면 실패
                if(nowSubArrCnt == k) return false;
            }
            now += nums[i];
        }
        return true;
    }
}