Title Requirements
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 = 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.
A positive integer array of length n is divided into m non-empty continuous subarrays, and the sum of all elements in each subarray is calculated separately.Find a division method that produces the largest subarray and the smallest of all the division methods.
For example, in the title, nums = [7,2,5,10,8], m = 2
There are four ways to split:
- [7], [2,5,10,8]
- [7,2], [5,8,10]
- [7,2,5], [8,10]
- [7,2,5,8], [10]
The sum of the largest subarray resulting from the third division is the smallest of all the divisions
Idea one: Dynamic planning
First, we can iterate through all the partitioning methods recursively to find the one that best meets the requirements of all the partitioning methods.The code is as follows:
public int splitArray(int[] nums, int m) { //Calculate the sum of all elements in [0...i] int[] sums = new int[nums.length+1]; for(int i = 1 ; i<=nums.length ; i++) { sums[i] = nums[i-1] + sums[i-1]; } return splitArray(nums, m, 0, sums); } //Calculate the minimum split scene starting at the cur position and dividing it into m subarrays public int splitArray(int[] nums, int m, int cur, int[] sums) { if(m == 1) { return sums[nums.length] - sums[cur]; } int min = Integer.MAX_VALUE; int diff = Integer.MAX_VALUE; for(int i = cur+1 ; i<=nums.length-m+1 ; i++) { //So far as the current element is concerned, the elements of the subarray on the left and int left = sums[i]-sums[cur]; //Recursive call to splitArray method for remaining elements on the right int right = splitArray(nums, m-1, i, sums); //If there is an incremental difference between the two, it means that the distance from the optimal partition is getting farther and farther, then stop trying if(diff < Math.abs(left - right)) { break; } diff = Math.abs(left - right); min = Math.min(min, Math.max(left, right)); } return min; }
This method will time out in large data scenarios, essentially because we don't have enough reuse of all the scenarios in the middle, such as the optimal result of k-slices of [i-j] this subarray.If we record the optimal result of k-splitting from I to the end of the array, which is recorded as dp[i][k], then the optimal result of k+1 splitting from J to the end of the array is min(max(num(j), dp[j+1][k]), max(nums(j)+num(j+1), dp[j+2][k]...)
The code is as follows:
public int splitArray(int[] nums, int m) { int L = nums.length; //Record elements of 0-i and int[] S = new int[L+1]; S[0]=0; for(int i=0; i<L; i++) S[i+1] = S[i]+nums[i]; //If m=1, the minimum split result corresponds to the sum of all elements in the entire array int[] dp = new int[L]; for(int i=0; i<L; i++) dp[i] = S[L]-S[i]; for(int s=1; s<m; s++) { for(int i=0; i<L-s; i++) { dp[i]=Integer.MAX_VALUE; for(int j=i+1; j<=L-s; j++) { int t = Math.max(dp[j], S[j]-S[i]); if(t<=dp[i]) dp[i]=t; else break; } } } return dp[0]; }
Idea two: dichotomy
This is a very difficult method to think of.The difficulty of dichotomy has always been how to divide the initial boundary and how to gradually reduce it and ensure that the left and right pointers can meet.Here, the boundary is set to the minimum and maximum sum of the elements of the subarray that can be obtained in the array.
As a general rule of thumb, the maximum element of an array determines the lower bound for the sum of the elements of a subarray that the array is divided into, and the elements and upper bounds of the array must not exceed the sum of all the elements of the array.
Once you have determined the upper and lower bounds for the sum of array elements, you need to find a way to continuously compress the intervals until the last one.
You can use the middle position as the boundary for the sum of array elements, assuming that the sum of all consecutive arrays does not exceed the mid value.If the split result obtained in this way is larger than the specified m, it means that the mid value as the maximum element and upper bound cannot split only m subarrays, so the maximum element and upper bound must be between the mid and the bound.Similarly, if the split result obtained in this way is less than or equal to the specified m, then the mid value as the maximum element and upper bound can satisfy the split of M subarrays, but there may be a better solution.The final result from this dichotomy is the minimum desired result.
public int splitArray2(int[] nums, int m) { long sum = 0; int max = Integer.MIN_VALUE; for(int i = 0 ; i<nums.length ; i++) { max = Math.max(max, nums[i]); sum += nums[i]; } if(m == 1) { return (int)sum; } long lft = max; long rgt = sum; while(lft <= rgt) { long mid = (lft + rgt) / 2; if(valid(nums, m, mid)) { rgt = mid - 1; }else { lft = mid + 1; } } return (int) lft; } public boolean valid(int[] nums, int m, long target) { int count = 1; long sum = 0; for(int i = 0 ; i<nums.length ; i++) { sum += nums[i]; if(sum > target) { sum = nums[i]; count++; if(count > m) { return false; } } } return true; }