410. Split Array Largest Sum - cocoder39/coco39_LC GitHub Wiki

410. Split Array Largest Sum

Suppose m = 1, then the result is high; suppose m = sz, then result is low. Hence, the final result is within [low, high] => binary search to enumerate mid, check if mid is valid in O(sz) time.

tip:

  • set cnt to 1 at the begin of helper(), then there is no need to increase cnt at the end of nums.
  • helper() returns bool is fine, there is no need to tell cnt > count, cnt == count, cnt < count. Only distinguish cnt > count and cnt <= count work.

(1) at binary search stage, cnt < count and cnt == count result in same behavior, decrease the sum of each segment.

(2) at final result checking stage, even if cnt < count, low is still the final result because high would result in a further smaller cnt.

time complexity is O(sz * log high).

class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        long low = INT_MIN, high = 0;
        for (int i = 0; i < nums.size(); i++) {
            low = max(low, (long)nums[i]);
            high += nums[i];
        }
        
        while (low + 1 < high) {
            long mid = low + (high - low) / 2;
            if (helper(nums, mid, m)) {
                high = mid;
            } else {
                low = mid;
            }
        }
        if (helper(nums, low, m)) {
            return low;
        } else {
            return high;
        }
    }
private:
    bool helper(vector<int>& nums, long sum, int count) {
        long s = 0;
        int cnt = 1;
        for (int i = 0; i < nums.size(); i++) {
            if (s + nums[i] > sum) {
                s = nums[i];
                cnt++;
                if (cnt > count)    return false;
            } else {
                s += nums[i];
            }
        }
        return true;
    } 
};
⚠️ **GitHub.com Fallback** ⚠️