[LeetCode] Split Array Largest Sum - Binary Search

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

Split Array Largest Sum - LeetCode

class Solution {
public:
    bool decide(vector<int>& nums, int k, int m){
        int cnt = 0;
        
        int add = 0;
        for(int i=0; i<nums.size(); i++){
            add += nums[i];
            
            if(add==k){
                add = 0;
                cnt++;
            }
            else if(add>k){
                add = nums[i];
                cnt++;
            }
        }
        
        if(add>0) cnt++;
        
        
        return cnt<=m;
    }
    
    
    
    int splitArray(vector<int>& nums, int m) {
        int lo = 0;
        int hi = 0;
        int maxx = 0;
        for(int i=0; i<nums.size();i++){
            hi += nums[i];
            maxx = max(maxx, nums[i]);
        }
        
        
        while(lo<=hi){
            int mid = (lo+hi)/2;
            
            if(mid>=maxx && decide(nums, mid, m)){
                hi = mid-1;
            }
            else{
                lo = mid+1;
            }
        }
        
        return lo;
    }
};