网站logo设计教程,设计上海兼职网站建设,wordpress做个游戏,建行想要精通算法和SQL的成长之路 - 分割数组的最大值 前言一. 分割数组的最大值1.1 二分法 前言 想要精通算法和SQL的成长之路 - 系列导航 一. 分割数组的最大值
原题链接 首先面对这个题目#xff0c;我们可以捕获几个关键词#xff1a;
非负整数。非空连续子数组。
那么我… 想要精通算法和SQL的成长之路 - 分割数组的最大值 前言一. 分割数组的最大值1.1 二分法 前言 想要精通算法和SQL的成长之路 - 系列导航 一. 分割数组的最大值
原题链接 首先面对这个题目我们可以捕获几个关键词
非负整数。非空连续子数组。
那么我们假设分割后的子数组和的最大值是M对应分割的子数组个数为N。他们之间必然存在以下关系
分割的子数组个数 N 越多对应的和最大值 M 也就越小。分割的子数组个数 N 越少对应的和最大值 M 也就越大。
那么我们以每组和的最大值作为切入点案例如下
设置 数组各自和的最大值 为 20此时分割依然是 [7, 2, 5, | 10, 8]此时分割的数组数为2。设置 数组各自和的最大值 为 19此时分割依然是 [7, 2, 5, | 10, 8]此时分割的数组数为2。设置 数组各自和的最大值 为 18此时分割依然是 [7, 2, 5, | 10, 8]此时分割的数组数为2。设置 数组各自和的最大值 为 17此时分割就变成了 [7, 2, 5, | 10, | 8]此时分割的数组数为3。
而我们题目要求分割组数是2那么满足这个条件的几种情况我们再取最大和最小的情况最终得到结果是18。
1.1 二分法
二分的目标对象是什么我们可以二分数组各自和的最大值。那么二分法就应该有初始区间
left可以是当前数组的最大元素值。单个元素一组right可以是当前数组的总和。所有元素成一组
那么我们二分后取得 mid
int mid left (right - left) / 2;接下来我们就要对数组进行分组计算了对数组从左往右按顺序分组使得分组后的各个子数组和不能超过mid。我们可以编写个helper函数
public int helper(int[] nums, int maxGroupSum) {// 分组数最小是1int res 1;int curSum 0;for (int num : nums) {// 如果加入当前元素会导致和超过限制那么就另外再分一组if (curSum num maxGroupSum) {res;curSum 0;}curSum num;}return res;
}我们计算好分组后的个数groupNum之后就需要和题目传入的k进行对比
groupNum k 说明数组各自和的最大值还是小了我们应该调大数组各自和的最大值。即left mid 1。反之right mid;
最终代码如下
public int splitArray(int[] nums, int k) {int max 0, sum 0;for (int num : nums) {max Math.max(max, num);sum num;}int left max, right sum;while (left right) {int mid left (right - left) / 2;// 如果分组数比 k 还要大说明每个分组的和最大值还是小了int groupNum helper(nums, mid);if (groupNum k) {left mid 1;} else {right mid;}}return left;
}public int helper(int[] nums, int maxGroupSum) {// 分组数最小是1int res 1;int curSum 0;for (int num : nums) {// 如果加入当前元素会导致和超过限制那么就另外再分一组if (curSum num maxGroupSum) {res;curSum 0;}curSum num;}return res;
}
