【LeetCode刷题】410. 分割数组的最大值

本文主要是介绍【LeetCode刷题】410. 分割数组的最大值，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 题目链接

410. 分割数组的最大值

2. 题目描述

3. 解题方法

题目中提到的是某个和的最大值是最小的，这种题目是可以用二分来解决的。

1. 确定区间，根据题目的数据范围，可以确定区间就是[0, 1e9]。
2. 每次找到的数，都要去check一下，看是否满足要求。
3. 满足的条件就是，是否有子数组刚好等于这个数并且子数组的个数还必须小于题目给的k。

4. 代码

class Solution {
public:int splitArray(vector<int>& nums, int k) {int l = 0, r = (int)1e9;while(l < r){int mid = (r - l) / 2 + l;if(check(mid, nums, k)) r = mid;else l = mid + 1;}return r;}bool check(int mid, vector<int>& nums, int k){int cnt = 1, sum = 0;for(auto e : nums){if(sum + e <= mid) sum += e;else {if(e > mid) return false;cnt ++;sum = e;}}return cnt <= k;}
};

最后附上我的打卡记录，希望各位大佬可以监督我一下。

这篇关于【LeetCode刷题】410. 分割数组的最大值的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---