LeetCode401：分割数组最大值

男娘i 2023-03-03 11:10 10阅读 0赞

### 文章目录 ###

*   *  LeetCode401： 分割数组最大值
     *   *  动态规划方法
         *  二分法
         *  后记

## LeetCode401： 分割数组最大值 ##

给定一个非负整数数组和一个整数 m，你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。

注意:  
数组长度 n 满足以下条件:

*  1 ≤ n ≤ 1000
 *  1 ≤ m ≤ min(50, n)

**示例**:

输入:
    nums = [7,2,5,10,8]
    m = 2
    
    输出:
    18
    
    解释:
    一共有四种方法将nums分割为2个子数组。
    其中最好的方式是将其分为[7,2,5] 和 [10,8]，
    因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。

**思考**：典型的二分查找问题，当然也有一些动态规划的影子在里面，在后续的时间里，会将关于这个题目所衍生出来的相关内容都进行一个整理。供学习参考。

关于动态规划相关题目有：

*  [1478: 安排邮筒][1478_]

关于二分查找相关题目有：

*  [69： 平方根][69_]
 *  [287：寻找重复数][287]。
 *  [875.：爱吃香蕉的珂珂（中等）][875.]
 *  [1011： 在 D 天内送达包裹的能力（中等）][1011_ _ D]
 *  [1482.：制作 m 束花所需的最少天wanzheng数（中等）][1482._ m _wanzheng]
 *  [LCP 12.：小张刷题计划（中等）][LCP 12.]

### 动态规划方法 ###

关于动态规划的思想： 说是可以分成m组，对于动态规划来说就是将一个完整的问题分割成为可以进行直接计算的微小部分，对于此道题目来说，我们就可以将1-i 划分为连续的m-1个子空间，然后将最后一个元素划分为最后一个空间，进行状态的转移处理

public int splitArray(int[] nums, int m) { 
     int [][] dp =new int [nums.length+1][m+1];
           // 首先是二维数组的定义
            // 然后是初始化，因为是求最小值 所以初始化为最大值
            for(int i =1;i<=nums.length;i++){ 
                Arrays.fill(dp[i],Integer.MAX_VALUE);
            }
          // 获取到当前位置（算上当前位置）的所有值的和
            int []sum = new int[nums.length+1];
          
            for(int i =1;i<=nums.length;i++){ 
                sum[i]=sum[i-1]+nums[i-1];
                // 保证不会出现对于一个元素，划分为两个空间的情况。
                int min=Math.min(i,m);
                for(int j =1;j<=min;j++){ 
                    // 若是直接划分为一个空间时候，就是进行所有数据的和。
                    if(j==1)
                        dp[i][1]=sum[i];
                    
                    else
                    { 
                        for(int k=1;k<i;k++){ 
                            // 进行状态的转移：当前的值和（前j-1组与最后一组的最大值）进行比较出来较小值。也就是状态的转移。
                            dp[i][j]=Math.min(dp[i][j],Math.max(dp[k][j-1],sum[i]-sum[k]));
                        }
                    }
                }
            }
            return dp[nums.length][m];
        }

### 二分法 ###

对于本题目来说要求进行分组，求得分组中的最大值最小，我们有两种极端的情况出现，一种是最小值为当前元素中的最大值（因为分组最多的情况，每一个元素也都是一个单独的个体），另一种情况就是将所有的元素都分成一个完整的小组，所以最大值就是所有元素的和。我们就利用二分法不断逼近这个中间值的同时也能够满足我们的分割的组数。

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 temp = getSplitNum(nums, mid);
                if (temp > m) { 
                    // 表示的是说，我们在完成分割之后的分割数要大于我们的要求分割数，表示分割多了，可是为什么会分割多呢？是因为我们的下限太低。所以进行下线的上调。
                    left = mid + 1;
                } else { 
                    // 进行上线的下调处理。
                    right = mid;
                }
            }
            return left;
        }
        private static int getSplitNum(int[] nums, int mid) { 
            // 表示最少是一个完整的数组。作为基础值。
            int split = 1;
            // 当前区间的和
            int currentSum= 0;
            for (int num : nums) { 
                // 若是我们当前区间的和要大于我们给定的空间的最大值时候，表示已经超出了我们的预算，我们本就是以最大值作为当前的最小值出现，若是超过了当前的最大值，就不能够选中进行相加的处理，我们就默认进行一次的分割，然后分割时候，不算上当前值的前面数组之和就必然小于我们假设的最大值。
                if (currentSum + num > mid) { 
                    // 进行下一轮的循环处理。
                    currentSum = 0;
                    split++;
                }
                currentSum += num;
            }
            return split;
        }
    }

### 后记 ###

对于二分法来说，涉及到的地方还是挺多，思想和思路也是蛮重要，后续会推出一篇具体讲解二分法的博客来将系列的文章理解清楚。

[1478_]: https://leetcode-cn.com/problems/allocate-mailboxes/
[69_]: https://leetcode-cn.com/problems/sqrtx/
[287]: https://leetcode-cn.com/problems/find-the-duplicate-number/
[875.]: https://leetcode-cn.com/problems/koko-eating-bananas/
[1011_ _ D]: https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days/
[1482._ m _wanzheng]: https://leetcode-cn.com/problems/minimum-number-of-days-to-make-m-bouquets/
[LCP 12.]: https://leetcode-cn.com/problems/xiao-zhang-shua-ti-ji-hua/