制作企业网站首页,如何查询网站建设者,电商设计专业,企业网站icp是什么文章目录1. 题目2. 解题2.1 二分查找2.2 DP1. 题目
给定一个非负整数数组和一个整数 m#xff0c;你需要将这个数组分成 m 个非空的连续子数组。 设计一个算法使得这 m 个子数组各自和的最大值最小。
注意:
数组长度 n 满足以下条件:
1 ≤ n ≤ 1000
1 ≤ m ≤ min(50, n)示…
文章目录1. 题目2. 解题2.1 二分查找2.2 DP1. 题目
给定一个非负整数数组和一个整数 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在所有情况中最小。来源力扣LeetCode 链接https://leetcode-cn.com/problems/split-array-largest-sum 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
2.1 二分查找
类似题目 LeetCode 875. 爱吃香蕉的珂珂二分查找 LeetCode LCP 12. 小张刷题计划二分查找 LeetCode 1011. 在 D 天内送达包裹的能力二分查找 LeetCode 1062. 最长重复子串二分查找 LeetCode 5438. 制作 m 束花所需的最少天数二分查找 LeetCode 1102. 得分最高的路径优先队列BFS/极大极小化 二分查找 LeetCode 1231. 分享巧克力极小极大化 二分查找
class Solution {
public:int splitArray(vectorint nums, int m) {long long l 0, r 1e15, maxsum, ans;while(l r){maxsum l((r-l)1);if(canSplitM(nums, maxsum, m))r maxsum-1, ans maxsum;elsel maxsum1;}return ans;}bool canSplitM(vectorint nums, long long maxsum, int m) {int count 0;long long sum 0;for(int i 0; i nums.size(); i){if(sumnums[i] maxsum)//和的最大值没有超过设定的maxsumsum nums[i];else//超过了{count;sum 0;i--;}if(count m)return false;}return true;}
};0 ms 7 MB
2.2 DP
dp[i][j] 表示前 i 个数分成 j 组的最小的最大和的值先预处理求出前缀和 sumdp[i][j]min(dp[i][j],max(dp[k][j−1],sum[i]−sum[k])),k∈[0,i]dp[i][j] min(dp[i][j], max(dp[k][j-1], sum[i]-sum[k])), k \in[0,i]dp[i][j]min(dp[i][j],max(dp[k][j−1],sum[i]−sum[k])),k∈[0,i]
class Solution {
public:int splitArray(vectorint nums, int m) {int n nums.size(), i, j, k;vectorlong long sum(n1, 0);for(i 1; i n; i)sum[i] sum[i-1] nums[i-1];vectorvectorlong long dp(n1, vectorlong long(m1,1e15));dp[0][0] 0;for(i 1; i n; i)for(j 1; j min(i,m); j)for(k 0; k i; k)dp[i][j] min(dp[i][j], max(dp[k][j-1], sum[i]-sum[k]));return dp[n][m];}
};412 ms 8.2 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
