[Leetcode][第410题][JAVA][分割数组的最大值][动态规划][二分]

╰+攻爆jí腚メ 2023-03-01 12:23 57阅读 0赞

#### 【问题描述】\[中等\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]

#### 【解答思路】 ####

###### 1. 动态规划 ######

**第 1 步：设计状态**  
令 f\[i\]\[j\] 表示将数组的前 i 个数分割为 j 段所能得到的最大连续子数组和的最小值。 （ i ≥ j ）  
**第 2 步：状态转移方程**  
![在这里插入图片描述][20200725111559124.png]

**第 3 步：考虑初始化**  
f\[i\]\[j\] = Integer.MAX\_VALUE  
f\[0\]\[0\]=0  
**第 4 步：考虑输出**  
f\[n\]\[m\]f\[n\]\[m\]

**复杂度**  
![在这里插入图片描述][20200725112220217.png]

class Solution { 
        public int splitArray(int[] nums, int m) { 
            int n = nums.length;
            int[][] f = new int[n + 1][m + 1];
            for (int i = 0; i <= n; i++) { 
                Arrays.fill(f[i], Integer.MAX_VALUE);
            }
            int[] sub = new int[n + 1];
            for (int i = 0; i < n; i++) { 
                sub[i + 1] = sub[i] + nums[i];
            }
            f[0][0] = 0;
            for (int i = 1; i <= n; i++) { 
                for (int j = 1; j <= Math.min(i, m); j++) { 
                    for (int k = 0; k < i; k++) { 
                        f[i][j] = Math.min(f[i][j], Math.max(f[k][j - 1], sub[i] - sub[k]));
                    }
                }
            }
            return f[n][m];
        }
    }

###### 2. 二分+贪心 ######

![在这里插入图片描述][20200725112709129.png]  
nums = \[7,2,5,10,8\]  
m = 1，那么整个数组作为一部分，最小的最大值为 32  
m = n，那么每个元素作为一个子数组，从所有元素选取最大值，最小的最大值小为 10  
**m 的取值范围为 1 <= m <= n，因此，最大值的最小值的范围为 \[10, 32\]**  
我们利用二分法查找，找出符合 m 的最大值的最小的结果  
二分过程：  
left = 10;  
right = 32  
mid = (left + right) >>> 1 = 21（这个 21 就是一个子数组的最大容量）  
我们假设刚开辟的用来存储的子数组个数 cnt = 1  
那么根据贪心思想，我们将数组元素按顺序逐个往里放  
因此就有如下过程：  
7 < 21  
7 + 2 < 21  
7 + 2 + 5 < 21  
7 + 2 + 5 + 10 > 21  
至此，我们可以看出一个 21 容量的子数组是无法容纳整个数组元素的，因此我们需要开辟第二个子数组来存储剩下的数组元素  
cnt = cnt + 1 = 2  
10 < 21  
10 + 8 < 21  
我们发现，两个子数组可以将整个数组元素放入，而 cnt 刚好等于 m，因此 \[7,2,5\] 和 \[10,8\] 就是分割出来的两个子数组，最小的最大值为 18

**区间缩小 （建议在草稿纸上模拟过程）**

1.  \[10.31\]
2.  \[10.21\]
3.  \[16,21\]
4.  \[16,18\]
5.  \[17.18\]
6.  \[18.18\]

为什么是放入元素直到放不下为止？因为要求的是连续子数组，我们需要保证每个连续的子数组的元素和都尽可能的接近 21

**如果我们最终得到的 cnt > m，那么表示我们划分出太多的子数组，也就是意味着一个子数组的容量太少，我们需要再扩大容量，即 left = mid + 1，然后继续进行二分  
如果我们最终得到的 cnt < m，那么表示我们划分出太少的子数组，也就是意味着一个子数组的容量太大，需要减少容量，即 right = mid**  
**复杂度**  
![在这里插入图片描述][20200725114648328.png]

public class Solution { 
    
        public int splitArray(int[] nums, int m) { 
            int max = 0;
            int sum = 0;
    
            // 计算「子数组各自的和的最大值」的上下界
            for (int num : nums) { 
                max = Math.max(max, num);
                sum += num;
            }
    
            // 使用「二分查找」确定一个恰当的「子数组各自的和的最大值」，
            // 使得它对应的「子数组的分割数」恰好等于 m
            int left = max;
            int right = sum;
            while (left < right) { 
                int mid = left + (right - left) / 2;
    
                int splits = split(nums, mid);
                if (splits > m) { 
                    // 如果分割数太多，说明「子数组各自的和的最大值」太小，此时需要将「子数组各自的和的最大值」调大
                    // 下一轮搜索的区间是 [mid + 1, right]
                    left = mid + 1;
                } else { 
                    // 下一轮搜索的区间是上一轮的反面区间 [left, mid]
                    right = mid;
                }
            }
            return left;
        }
    
        /*** * * @param nums 原始数组 * @param maxIntervalSum 子数组各自的和的最大值 * @return 满足不超过「子数组各自的和的最大值」的分割数 */
        private int split(int[] nums, int maxIntervalSum) { 
            // 至少是一个分割
            int splits = 1;
            // 当前区间的和
            int curIntervalSum = 0;
            for (int num : nums) { 
                // 尝试加上当前遍历的这个数，如果加上去超过了「子数组各自的和的最大值」，就不加这个数，另起炉灶
                if (curIntervalSum + num > maxIntervalSum) { 
                    curIntervalSum = 0;
                    splits++;
                }
                curIntervalSum += num;
            }
            return splits;
        }
    
        public static void main(String[] args) { 
            int[] nums = new int[]{ 7, 2, 5, 10, 8};
            int m = 2;
            Solution solution = new Solution();
            int res = solution.splitArray(nums, m);
            System.out.println(res);
        }
    }

#### 【总结】 ####

###### 1. 动态规划流程 ######

第 1 步：设计状态  
第 2 步：状态转移方程  
第 3 步：考虑初始化  
第 4 步：考虑输出  
第 5 步：考虑是否可以状态压缩

###### 2.细节 ######

Arrays.fill()并不能提高赋值的效率，在函数的内部也是用for循环的方式 实现的。  
fill()函数源码：

public static void fill(Object[] a, Object val) { 
            for (int i = 0, len = a.length; i < len; i++)
                a[i] = val;
        }

for (int i = 0; i <= n; i++) { 
                Arrays.fill(f[i], Integer.MAX_VALUE);
            }

**等价于**

for (int i = 0; i <= n; i++) { 
                for(int j =0 ;j<=m;j++){ 
                   f[i][j] = Integer.MAX_VALUE;
                }
            }

###### 3.审题认真！ Java函数不懂可以看源码， 效率超高！（总比瞎猜好） ######

参考链接：https://leetcode-cn.com/problems/split-array-largest-sum/solution/er-fen-cha-zhao-by-liweiwei1419-4/  
参考链接：https://leetcode-cn.com/problems/split-array-largest-sum/solution/fen-ge-shu-zu-de-zui-da-zhi-by-leetcode-solution/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: /images/20230208/aee3ab554c7d499598de6e9f10acc226.png
[20200725111559124.png]: /images/20230208/6fc75f32294f4258964a41b9ef56e0be.png
[20200725112220217.png]: /images/20230208/809127d9879c4dcd85ab4d52c90f22bd.png
[20200725112709129.png]: /images/20230208/42bea05e8ea047c0845a327d18fef7af.png
[20200725114648328.png]: /images/20230208/eda8c52982344a0da0846bd5df0e6ec3.png