# Easy C++ binary search solution with explanation

• Since subarrays are non empty, and numbers are non-negative, result can be no less than max element in the array. It also can not be more than the sum of array elements. We now have min and max possible answers and can use binary search to get the exact result

bool splits(vector<int>& nums, int m, long max_largest_sum)
{
long cur_subarray_sum = nums[0];
int nsubarays = 1;
for(int i = 1; i < nums.size(); ++i)
{
cur_subarray_sum += nums[i];
if(cur_subarray_sum > max_largest_sum)
{
++nsubarays;
cur_subarray_sum = nums[i];
}
}
if(nsubarays > m)
return false;
return true;
}
int splitArray(vector<int>& nums, int m) {
int n = nums.size();
long minres = nums[0], maxres = nums[0];
for(int i = 1; i < n; ++i)
{
minres = max(minres,long(nums[i]));
maxres += nums[i];
}
int res = 0;
while(minres <= maxres)
{
long mid = (minres+maxres)/2;
if(splits(nums,m,mid))
{
maxres  = mid-1;
res = mid;
}
else
minres = mid+1;
}
return res;
}

• This post is deleted!

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