C++プログラムで少なくともk個の離れた要素を持つ最大合計サブシーケンス

この問題では、サイズnと数kの配列arr[]が与えられます。私たちのタスクは、少なくともk個の離れた要素を持つ最大の合計サブシーケンスを見つけるプログラムを作成することです。

問題の説明 −サブ配列の要素が、インデックスがkの距離にあり、合計が最大化される配列から取得されるように、サブ配列の合計を見つける必要があります。

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

入力

arr[] = {2, 3, 7, 9, 2, 8, 3}

出力

15

説明

All subsequences that satisfy the given condition,
{2, 9, 3}, Sum = 14
{3, 2}, Sum = 5
{7, 8}, Sum = 15

ソリューションアプローチ

この問題の簡単な解決策は、与えられた条件を満たすすべての可能なサブアレイを見つけることです。すべての配列の合計を見つけて、すべての最大値を返します。

この問題のより効率的な解決策は、現在の要素までの最大合計を格納する配列を作成することにより、動的プログラミングアプローチを使用することです。現在の要素については、合計として考慮するか、合計として破棄して、現在のインデックスまで合計を増やす方を選択できます。

合計として考える場合、sum [i] =sum [i + k + 1] + arr [i + 1]それ以外の場合は、合計として破棄します。sum[i] =sum [i+1]そして最後にsum[0]にある最大合計を返します。

例

ソリューションの動作を説明するプログラム

#include <bits/stdc++.h>
using namespace std;
int calcMaxSubSeqSum(int arr[], int N, int k){
   int maxSumDP[N];
   maxSumDP[N − 1] = arr[N − 1];
   for (int i = N − 2; i >= 0; i−−) {
      if (i + k + 1 >= N)
         maxSumDP[i] = max(arr[i], maxSumDP[i + 1]);
      else
         maxSumDP[i] = max(arr[i] + maxSumDP[i + k + 1], maxSumDP[i + 1]);
   }
   return maxSumDP[0];
}
int main() {
   int N = 10, k = 2;
   int arr[] = { 50, 70, 40, 50, 90, 70, 60, 40, 70, 50 };
   cout<<"The maximum sum subsequence with at−least k distant elements is "<<calcMaxSubSeqSum(arr, N, k);
   return 0;
}

出力

The maximum sum subsequence with at-least k distant elements is 230