410. Split Array Largest Sum
1. Description
Given an integer array nums and an integer k, split nums into k non-empty subarrays such that the largest sum of any subarray is minimized.
Return the minimized largest sum of the split.
A subarray is a contiguous part of the array.
2. Example
Example 1:
Input: nums = [7,2,5,10,8], k = 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], k = 2
Output: 9
Explanation: There are four ways to split nums into two subarrays.
The best way is to split it into [1,2,3] and [4,5], where the largest sum among the two subarrays is only 9.
3. Constraints
- 1 <= nums.length <= 1000
- 0 <= nums[i] <= $10^6$
- 1 <= k <= min(50, nums.length)
4. Solutions
Binary Search & Greedy
n = nums.size()
Time complexity: O(nlog(sum(nums) - max(nums)))
Space complexity: O(1)
class Solution {
private:
int check(const vector<int> &nums, int sum_limit, int k) {
// greedy
// this problem asks for contiguous subarray, otherwise it will be much complex
int max_sum = 0;
for (int i = 0, sum = 0; i < nums.size(); ++i) {
sum += nums[i];
if (sum > sum_limit) {
--k;
sum = nums[i];
}
max_sum = max(max_sum, sum);
}
return k >= 1 ? max_sum : -1;
}
public:
int splitArray(const vector<int> &nums, int k) {
int max_num = 0, nums_sum = 0;
for (int num : nums) {
max_num = max(max_num, num);
nums_sum += num;
}
int result = 0;
for (int left = max_num, right = nums_sum; left <= right;) {
int mid = (left + right) / 2;
int check_result = check(nums, mid, k);
// be careful of this (), the order of ":" > ","
check_result == -1 ? left = mid + 1 : (right = mid - 1, result = check_result);
}
return result;
}
};