分割数组的最大值问题

分割数组的最大值问题

作者：Grey

原文地址：

博客园：分割数组的最大值问题

CSDN：分割数组的最大值问题

题目说明

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

在线测评见：LeetCode 410. Split Array Largest Sum

主要思路

我们先求整个数组的累加和，假设累加和为 sum，我们可以得到一个结论：

分割的 m 个非空连续子数组，每个数组内元素之和的范围一定在(0,sum]区间内。

如果某种划分下的子数组之和的最大值为 max，则 max 首先肯定在(0,sum]区间内。

所以我们可以尝试将思路转换为：

我们先设置一个 max，子数组的累加和最大值不能超过 max 的情况下，最少可分多少部分？

假设能分 k 个部分，

如果k <= m，说明设置的 max 这种划分是满足条件的，再看 max 是否可以变的更小。

如果k > m，说明设置的 max 这种划分是不满足条件的，需要调大 max 的值。

我们可以通过二分的方式来定位 max 的值。即 max 先取(0,sum]的中点值，得到的划分部分数量为 k， 如果k <= m，则 max 继续去左边取中点位置来得到新的划分 k，

如果k > m，max 继续从右边的中点位置来得到新的划分 k 。

完整代码

class Solution {     public static int splitArray(int[] nums, int m) {         int sum = 0;         for (int num : nums) {             sum += num;         }         int l = 0;         int r = sum;         int ans = 0;         while (l <= r) {             int mid = l + ((r - l) >> 1);             int parts = getParts(nums, mid);             if (parts > m) {                 // mid越大，parts才会越小                 l = mid + 1;             } else {                 ans = mid;                 r = mid - 1;             }         }         return ans;     }      // 达到aim要分几部分     public static int getParts(int[] nums, int aim) {         for (int num : nums) {             if (num > aim) {                 return Integer.MAX_VALUE;             }         }         int part = 1;         int all = nums[0];         for (int i = 1; i < nums.length; i++) {             if (all + nums[i] > aim) {                 part++;                 all = nums[i];             } else {                 all += nums[i];             }         }         return part;     } } 

其中：int getParts(int[] nums, int aim)方法表示：

在连续子数组之和不超过 aim 的情况下，最少需要几个划分部分。

方法的主要逻辑是：

遍历数组，

如果发现某个元素的值超过了 aim，直接返回系统最大，说明无法得到划分。

如果没有超过 aim，则继续加入下一个元素，直到超过 aim，就定位出一个部分。依次类推，就可以得到最少有几个划分。

由于不回退机制，整个算法时间复杂度 O(N)。

更多地，此题也可以用四边形不等式优化的动态规划来解，但是最优解是二分法。

更多

算法和数据结构笔记