410. Split Array Largest Sum

410. Split Array Largest Sum

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

Note: If n is the length of array, assume the following constraints are satisfied:

1 ≤ n ≤ 1000 1 ≤ m ≤ min(50, n) Examples:

Input:nums = [7,2,5,10,8]m = 2Output:18Explanation: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.

Algorithm： We can use Binary search to find the value x0. Keeping a value mid = (left + right) / 2. If F(mid) is false, then we will search the range [mid + 1, right]; If F(mid) is true, then we will search [left, mid - 1].

For a given x, we can get the answer of F(x) using a greedy approach. Using an accumulator sum to store the sum of the current processing subarray and a counter cnt to count the number of existing subarrays. We will process the elements in the array one by one. For each element num, if sum + num <= x, it means we can add num to the current subarray without exceeding the limit. Otherwise, we need to make a cut here, start a new subarray with the current element num. This leads to an increment in the number of subarrays.

After we have finished the whole process, we need to compare the value cnt to the size limit of subarrays m. If cnt <= m, it means we can find a splitting method that ensures the maximum largest subarray sum will not exceed x. Otherwise, F(x) should be false.

class Solution public int splitArray(int[] nums, int m) { long l = 0; long r = 0; int n = nums.length; for (int i = 0; i < n; i++) { r += nums[i]; if (l < nums[i]) { l = nums[i]; } } long ans = r; while (l <= r) { long mid = (l + r) >> 1; long sum = 0; int cnt = 1; for (int i = 0; i < n; i++) { if (sum + nums[i] > mid) { cnt ++; sum = nums[i]; } else { sum += nums[i]; } } if (cnt <= m) { ans = Math.min(ans, mid); r = mid - 1; } else { l = mid + 1; } } return (int)ans; }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。