C++で配列の最大合計を分割

正の整数の配列と1つの値mがあるとします。この配列をm個の連続するサブ配列に分割できます。これらのm個のサブアレイの中で最大の合計を最小化するアルゴリズムを考案する必要があります。

したがって、配列が[7,2,4,10,9]であり、m =2の場合、[7,2,4]と[10,9]のような2つのサブ配列を作成できるため、合計は19になります。 、合計が最大のサブ配列は19です。

これを解決するには、次の手順に従います-

• 関数splitArray（）を定義します。これには、配列v、mが必要です。
• n：=vのサイズ
• サイズの1つの配列dpを作成します
• サイズnの別の配列の合計を作成します
• sum [0]：=v [0]
• iを初期化する場合：=1、i
• sum [i]：=sum [i-1] + v [i]

理解を深めるために、次の実装を見てみましょう-

例

#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