[LeetCode]410. Split Array Largest Sum三种不同解法(JavaScript)
题目描述
LeetCode原题链接：410. Split Array Largest Sum
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)
解法一：不知道该叫什么那就叫摸着石头过河吧！
要想求一个每个子数组中元素和的最小值，那肯定是要确保这些子数组的和之间差值较小，也就是说我们要尽可能的平分。假设数组中所有元素之和为sum，需要分割成m个子数组，那么每一个子数组的和至少要是 minSum = sum/m 才能保证尽可能的平分。当然，这这只是理想情况，因为sum不一定能整除m（有余数的话分组数就多于m了），而且题目要求是连续的元素组成的子数组，合法的子数组的和不一定刚好能凑成minSum（如果存在一个或多个子数组的和 所以这个解法的思路概括一下就是： 1. 根据nums的和还给定的m求出一个下限值minSum； 2. 遍历nums数组进行分割，分割条件是当前subArray的和<=minSum; 3. 如果nums数组还没遍历结束已经分出的子数组的个数大于m，说明当前minSum过小，minSum++再重复2.；如果nums数组遍历完成且分出的子数组数等于m，说明找到了结果，直接返回。 上述的解法效率有点低，因为minSum每次只自增1去重新判断。那么有没有什么办法可以加速这个过程呢？当然，我们可以用二分法！二分法需要知道查找的左右边界，我们已经得出下限了，那上限是什么呢？如果m=1，也就是说只分割出一个子数组且这个子数组是其自身，这个时候子数组的和就是整个数组的和，肯定是最大的。很好，下面我们来看如何移动中点。和前面分析的差不多，我们用中点值去分割数组时，根据分割出的子数组个数来判断当面的分割标准是偏大还是偏小：如果分割出的组数大于m，则需要扩大minSum，即将左指针右移；如果恰好可以分割成m组，就缩小当前的minSum，即将右指针左移，去找更优解。 换个思路，我们建立一个二维数组，dp[i][j]表示前j个数字如果分成i组各子数组和的最小值。下面我们来推导状态转移方程。对于前j各数组，我们分组的情况是分成1组、2组、3组......j组；即最小分成1组，最多分成j组。那么我们在尝试从1组到j组的分组，即遍历中间态k时，可以知道dp[i-1][k]表示数组中前k个数字分成i-1组时各子数组和的最小值，我们用这个最小值和[k,j]位置的这个子数组的和比较，取两者中较大的那个和之前的dp[i][j]比较，再取较小值来更新dp[i][j]（局部最大值，全局最小值）。为了快速求[k,j]范围内所有元素和，我们可以用一个前缀和数组来处理：即一次遍历并保存[0,i]范围的元素和，那么要求[i,j]范围内的元素和只需用sum[0, j] - sum[0, i]即可。 1 var splitArray = function(nums, m) {
2 let sum = 0;
3 nums.forEach((num, i) => {
4 sum += num;
5 });
6 let minSum = Math.floor(sum / m); // 求下限值
7 while(!canSplit(nums, m, minSum)) {
8 minSum++;
9 }
10 return minSum;
11 };
12
13 // 校验分组合法性
14 var canSplit = function(nums, m, minSum) {
15 let cnt = 0;
16 let i = 0;
17 while(i < nums.length) {
18 if(cnt == m) return false;
19 let j = i;
20 let temp = 0;
21 while(j < nums.length && temp + nums[j] <= minSum)
22 {
23 temp += nums[j++];
24 }
25 cnt++;
26 i = j;
27 }
28 return true;
29 }
解法二：Binary Search
1 var splitArray = function(nums, m) {
2 let right = 0;
3 let left = 0;
4 nums.forEach((num) => {
5 right += num;
6 });
7 left = Math.floor(right / m);
8 while(left < right) {
9 let minSum = Math.floor((left + right) / 2);
10 if(!canSplit(nums, m, minSum)) {
11 left = minSum + 1;
12 }
13 else {
14 right = minSum;
15 }
16 }
17 return right;
18 };
19
20 var canSplit = function(nums, m, minSum) {
21 let cnt = 0;
22 let i = 0;
23 while(i < nums.length) {
24 if(cnt == m) return false;
25 let j = i;
26 let temp = 0;
27 while(j < nums.length && temp + nums[j] <= minSum)
28 {
29 temp += nums[j++];
30 }
31 cnt++;
32 i = j;
33 }
34 return true;
35 }
解法三：动态规划
1 var splitArray = function(nums, m) {
2 let len = nums.length;
3 let prefixSum = new Array(len + 1);
4 prefixSum.fill(0);
5 let dp = new Array(m + 1);
6 for(let i = 0; i <= m; i++) {
7 dp[i] = new Array(len + 1);
8 for(let j = 0; j <= len; j++) {
9 dp[i][j] = Number.MAX_VALUE;
10 if(j > 0) {
11 prefixSum[j] = prefixSum[j - 1] + nums[j - 1];
12 }
13 }
14 }
15 dp[0][0] = 0;
16 for(let i = 1; i <= m; i++) {
17 for(let j = 1; j <= len; j++) {
18 for(let k = i - 1; k < j; k++) {
19 dp[i][j] = Math.min(dp[i][j], Math.max(prefixSum[j] - prefixSum[k], dp[i-1][k]));
20 }
21 }
22 }
23 return dp[m][len];
24 };