410. Split Array Largest Sum

Description

Given an array nums 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.

Example 1:

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.

Example 2:

Input: nums = [1,2,3,4,5], m = 2
Output: 9

Example 3:

Input: nums = [1,4,4], m = 3
Output: 4

Constraints:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 106
• 1 <= m <= min(50, nums.length)

---

Solutions

Solution 1

Intuition

1. Binary search
2. greedy
3. mid means the largest sum of split part
4. split the array into many parts, the maximum sum of each part is the mid/largest, and see how many parts are needed — cnt, make sure cnt ≤ m

Code

class Solution {
public:
    bool check(vector<int>& nums, int m, int largest) {
        int sum = 0, cnt = 0;
        for (int x : nums) {
            if (x > largest) return false;
            if (sum + x > largest) {
                sum = x;
                cnt++;
            } else {
                sum += x;
            }
        }
        if (sum >= 0) cnt++;
        return cnt <= m;
    }
    int splitArray(vector<int>& nums, int m) {
        int l = 0, r = INT_MAX, mid;
        while (l < r) {
            mid = l + r >> 1;
            if (check(nums, m, mid))
                r = mid;
            else
                l = mid + 1;
        }
        return l;
    }
};

Complexity

• Time: O(nlogs)
• Space: O(1)