連続する繰り返しがC++でKを超えないように、最大​​合計M要素を選択します

この問題では、配列arr []と2つの整数MおよびKが与えられます。私たちのタスクは、与えられた配列の要素を使用して配列を作成することです。新しい配列のサイズはMである必要があり、Kより大きいサイズのサブ配列はすべての要素を同じにすることはできません。作成された配列によって可能な最大の合計を出力する必要があります。

問題を理解するために例を見てみましょう

入力 − arr [] ={1、2、4、5、7}、M =5、K =2

説明 − {7、7、5、7、7}の条件を満たす配列が作成されました。ここでは、サイズが2を超えるサブ配列ですべての要素を同じにすることはできません。

この問題を解決するには、最大値を持つ要素を使用して配列を作成する必要があります。ただし、max要素をk回以上使用することはできないため、k回を超えると、配列の2番目のmax要素を使用する必要があります。配列内のk個の最大値ごとに1秒の最大値を挿入し、Mの長さの配列を作成します。最終的な出力は、この配列のすべての要素の合計になります。

例

ソリューションの実装を示すプログラム

#include <iostream>
using namespace std;
long int arraySum(int arr[], int n, int m, int k){
   int max1 = arr[0], max2 = arr[0];
   for (int i = 1; i < n; i++) {
      if (arr[i] > max1) {
         max2 = max1;
         max1 = arr[i];
      }
      else if (arr[i] > max2)
         max2 = arr[i];
   }
   int max2count = m / (k + 1);
   long int sum = max2count * max2 + (m - max2count) * max1;
   return sum;
}
int main() {
   int arr[] = { 1, 3, 6, 7, 4, 5 };
   int n = sizeof(arr) / sizeof(arr[0]);
   int m = 9, k = 2;
   cout<<"The maximum sum of array created from the given array such that no subarray of size greater    than "<<k<<" will have same elements is ";
   cout<<arraySum(arr, n, m, k);
   return 0;
}

出力

The maximum sum of array created from the given array such that no subarray of size greater than 2 will have same elements is 60