15. Split Array Largest Sum

Link to the problem

Description

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:
If n is the length of array, assume the following constraints are satisfied:

• 1 ≤ n ≤ 1000
• 1 ≤ m ≤ min(50, n)

Example

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

Idea

Binary search for the minimum S, such that it's possible to group consecutive subarrays, each of sum at most S. To check feasibility for a given S, just greedily group consecutive elements whose sum do not exceed S.

Solution

class Solution {
private:
    int nSplit(vector<int> &nums, int thres) {
        int numSplit = 1;
        int curSum = 0;
        for (auto it = nums.begin(); it != nums.end(); it++) {
            if (curSum + *it > thres) {
                numSplit++;
                curSum = *it;
            } else {
                curSum += *it;
            }
        }
        return numSplit;
    }
public:
    int splitArray(vector<int>& nums, int m) {
        int lo = 0;
        int hi = 0;
        for (auto it = nums.begin(); it != nums.end(); it++) {
            hi += *it;
            lo = max(lo, *it);
        }
        // binary search for the minimum feasible largest sum
        while (lo < hi) {
            int mi = lo + (hi - lo) / 2;
            if (nSplit(nums, mi) <= m) {
                hi = mi;
            } else {
                lo = mi + 1;
            }
        }
        return lo;
    }
};

27 / 27 test cases passed.
Runtime: 3 ms