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[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），-
对于初始化结束：=开始+1，当结束<=n-i时，更新（将结束增加1），执行-
dp[start]：=dp[start]的最小值和最大值（当start为0时，sum[end-1]，否则为sum[end-1]-sum[start-1]）和dp[end]
对于initializestart==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