Split Array Largest Sum
Given an array of non-negative integers nums and an integer m, you need to split the array into m non-empty continuous subarrays where the largest sum of subarrays should be minimized.
Constraints:
- 1 <= nums.length <= 1000
- 1 <= m <= min(50, nums.length)
- 0 <= nums[i] <= 10^6
Examples:
Input: nums = [7,2,5,10,8], m = 2
Output: 18
Explanation: One possible way to split the array is [7,2,5] and [10,8]. The largest sum of subarrays is 18.
Solutions
Binary Search
The idea is to use binary search to find the minimum largest sum of subarrays. We start with the maximum possible sum (the sum of all elements) and the minimum possible sum (the maximum element in the array). We then try to find the middle value and check if we can split the array into m subarrays with sum less than or equal to the middle value. If we can, we update the high value to the middle value. If we cannot, we update the low value to the middle value plus one. We repeat this process until the low value is greater than or equal to the high value.
class Solution {
public: int splitArray(vector<int>& nums, int m) {
int low = INT_MAX, high = 0;
for (int num : nums) {
low = min(low, num);
high += num;
}
while (low < high) {
int mid = low + (high - low) / 2;
if (canSplit(nums, mid, m)) {
high = mid;
}
else {
low = mid + 1;
}
}
return low;
}
bool canSplit(vector<int>& nums, int max, int m) {
int count = 1, sum = 0;
for (int num : nums) {
sum += num;
if (sum > max) {
count++;
sum = num;
}
}
return count <= m;
}Follow-up:
What if the array is very large and we need to split it into a specific mechanisms {
