合計がC++で最大であるk個の重複しないサブリストの合計を見つけるプログラム

numsと呼ばれる数値のリストがあり、別の値kがあるとすると、それらの合計の合計が最大になるように、k個の重複しない空でないサブリストを見つける必要があります。 kはnumsのサイズ以下であると見なすことができます。

したがって、入力がnums =[11、-1、2、1、6、-24、11、-9、6] k =3の場合、サブリストを選択できるため、出力は36になります[11 、-1、2、1、6]、[11]、および[6]を使用して、[19、11、6]=36の合計を取得します。

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

• n：=numsのサイズ
• nが0と同じか、kが0と同じ場合、-
  • 0を返す
• サイズk+1の配列hiを定義し、-infで埋めます
• サイズk+1の別の配列を定義し、-infで埋めます
• hi [0]：=0
• numsの各num-
  • サイズk+1の配列nopenを定義し、-infで埋めます
  • iを初期化する場合：=1、i <=kの場合、更新（iを1つ増やす）、実行
    • open [i]> -infの場合、-
      • nopen [i]：=open [i] + num
    • hi [i-1]> -infの場合、-
      • nopen [i]：=nopen[i]とhi[i-1]+numの最大値
  • open：=move（nopen）
  • iを初期化する場合：=1、i <=kの場合、更新（iを1つ増やす）、実行
    • hi [i]：=hi[i]とopen[i]の最大値
• return hi [k]

例（C ++）

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

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int>& nums, int k) {
   int n = nums.size();
   if (n == 0 || k == 0)
      return 0;
   vector<int> hi(k + 1, INT_MIN), open(k + 1, INT_MIN);
   hi[0] = 0;
   for (int num : nums) {
      vector<int> nopen(k + 1, INT_MIN);
      for (int i = 1; i <= k; ++i) {
         if (open[i] > INT_MIN)
            nopen[i] = open[i] + num;
         if (hi[i - 1] > INT_MIN)
            nopen[i] = max(nopen[i], hi[i - 1] + num);
      }
      open = move(nopen);
      for (int i = 1; i <= k; ++i)
      hi[i] = max(hi[i], open[i]);
   }
   return hi[k];
}
int main(){
   vector<int> v = {11, -1, 2, 1, 6, -24, 11, -9, 6};
   int k = 3;
   cout << solve(v, 3);
}

入力

{11, -1, 2, 1, 6, -24, 11, -9, 6}, 3

出力

36