Split Array Largest Sum -- LeetCode 419

[Question]

Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.

Note:
Given m satisfies the following constraint: 1 ≤ m ≤ length(nums) ≤ 14,000.

Examples:

Input:
nums = [7,2,5,10,8]
m = 2

Output:
18

Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.

[Analysis]
The largest sum S of each sub-array after a split, is within the range of [max element of the array, sum of the array]. Considering each possible S, if S is too large, the array could be split only by a number less than m; if S is too small, the array will be split by a number larger than m.  So, using binary search, the minimal S will be found.

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