[C++] vector sum, vector max

 

LeetCode: 410. Split Array Largest Sum

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

Split Array Largest Sum - LeetCode

class Solution {
public:
    int splitArray(vector<int>& nums, int k) {
        int ret = accumulate(nums.begin(), nums.end(), 0);
        int left = *max_element(nums.begin(), nums.end());
        int right(ret);
        while (left <= right) {
            int mid = (left + right) / 2;
            int n = numGroups(nums, mid);
            if (n <= k) {
                ret = min(ret, mid);
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }
        return ret;
    }

    int numGroups(vector<int>& nums, int limit) const {
        int ret = 0;
        int total = 0;
        for (int num : nums) {
            total += num;
            if (total > limit) {
                total = num;
                ret++;
            }
        }
        return ret + 1;
    }
};