2つの要素が隣接しないような最大合計C++プログラムの代替メソッド

この問題では、正の値で構成されるサイズnの配列arr[]が与えられます。私たちのタスクは、配列の2つの連続する要素がないように、最大​​のサブシーケンス合計を見つけるプログラムを作成することです。

問題の説明 −配列の要素を持つサブ配列の合計を見つける必要がありますが、配列の2つの隣接する要素を考慮することはできません。

例

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

入力

arr[] = {5, 2, 1, 9, 6}

出力

説明 −

Subarray sum are :
{5, 1, 6}, sum = 5 + 1 + 6 = 12
{2, 9}, sum = 2 + 9 = 11

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

ここでは、動的プログラミングアプローチを使用している問題の代替ソリューションがあります。このアプローチでは、指定された条件を満たすサブシーケンスを見つけて、その最大値を出力します。作成されたサブシーケンスの最大サブを格納する配列maxSumDP[n]を作成します。要素maxSumDP[i]は、インデックスiからn-1までの要素を取得することによって作成されたサブシーケンスの最大合計を格納します。これについては、配列arr [i]の現在の要素、つまりmaxSumDP [i] =arr[i]+のいずれかを考慮することができます。 maxSumDP [i+2]。または、配列arr [i]の現在の要素、つまりmaxSumDP [i] =maxSumDP [i+2]を考慮しないでください。

アルゴリズム

初期化 −

maxSumDP[]

ステップ2 −

initialize the values of maxSumDP[n−1] and maxSumDP[n−2].
maxSumDP[n−1] = arr[n−1] and maxSumDP[n−2] = max(arr[n−1], arr[n−2]).

ステップ2 −

loop for i −> n−2 to 0

ステップ1.2 −

initialize the value of maxSumDP[i],
maxSumDP[i] = maximum of (arr[i] + maxSumDP[i + 2],
maxSumDP[i + 1])

ステップ3 −

Return maxSumDP[0] which is the maximum sum sequence sum.

例

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

#include <iostream>
using namespace std;
int retMaxVal(int a, int b){
   if(a > b)
   return a;
   return b;
}
int calcMaxSum(int arr[], int n){
   int maxSumDP[n];
   maxSumDP[n−1] = arr[n−1];
   maxSumDP[n−2] = max(arr[n−1], arr[n−2]);
   for (int i = n − 2; i >= 0; i−−) {
      maxSumDP[i] = retMaxVal(arr[i] + maxSumDP[i + 2],
      maxSumDP[i + 1]);
   }
   return maxSumDP[0];
}
int main() {
   int arr[] = { 5, 2 , 1, 9, 6 };
   int n = sizeof(arr) / sizeof(int);
   cout<<"The maximum subsequence sum in such a way that no two consecutive elements of the array is "<<calcMaxSum(arr, n);
   return 0;
}

出力

The maximum subsequence sum in such a way that no two consecutive
elements of the array is 14