数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中分割数组最大和
假设我们有一个正整数数组和一个值 m。我们可以将此数组分成 m 个连续的子数组。我们必须设计一种算法来最小化这 m 个子数组中最大的和。
所以如果数组是 [7,2,4,10,9]，并且 m = 2，那么和将是 19，因为我们可以创建两个子数组，如 [7,2,4] 和 [10,9]，然后子数组的最大和是 19。
为了解决这个问题，我们将遵循以下步骤 -
- 定义一个函数 splitArray()，它将接收一个数组 v、m，
- n := v 的大小
- 创建一个大小为 的 dp 数组
- 创建一个大小为 n 的 sum 数组
- sum[0] := v[0]
- 初始化 i := 1，当 i < n 时，更新（i 增加 1），执行 -
- sum[i] := sum[i - 1] + v[i]
- dp[0] := sum[n - 1]
- 初始化 i := 1，当 i < n 时，更新（i 增加 1），执行 -
- dp[i] := sum[n - 1] - sum[i - 1]
- 初始化 i := 1，当 i < m 时，更新（i 增加 1），执行 -
- 初始化 start := 0，当 start < n - i 时，更新（start 增加 1），执行 -
- 初始化 end := start + 1，当 end <= n - i 时，更新（end 增加 1），执行 -
- dp[start] := dp[start] 和 (当 start 为 0 时 sum[end - 1]，否则 sum[end - 1] - sum[start - 1]) 和 dp[end] 的最小值
- 初始化 start := 0，当 start < n - i 时，更新（start 增加 1），执行 -
- 返回 dp[0]
让我们看看以下实现以更好地理解 -
示例
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int splitArray(vector<int>& v, int m) {
int n = v.size();
vector <long long int > dp(n);
vector <long long int> sum(n);
sum[0] = v[0];
for(int i =1;i<n;i++)sum[i] =sum[i-1]+v[i];
dp[0] = sum[n-1];
for(int i =1;i<n;i++){
dp[i] = sum[n-1] - sum[i-1];
}
for(int i =1;i<m;i++){
for(int start = 0;start<n-i;start++){
for(int end = start+1;end<=n-i;end++){
dp[start] = min(dp[start],max((start==0?sum[end-1]:sum[end-1]-sum[start-1]),dp[end]));
}
}
}
return dp[0];
}
};
main(){
Solution ob;
vector<int> v = {7,2,4,10,9};
cout << (ob.splitArray(v, 2));
}输入
[7,2,4,10,9] 2
输出
19
更新于: 2020-06-01
332 次查看
广告