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 <= 10000 <= nums[i] <= 1061 <= m <= min(50, nums.length)
Solutions
Solution 1
Intuition
- Binary search
- greedy
-
midmeans thelargestsum of split part - 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 surecnt≤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)
Top comments (0)