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]

• 对于initialize 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