2つの要素が隣接しないような最大合計-C++で2を設定します

この問題では、配列arr[]が与えられます。私たちのタスクは、C++で2つの要素が隣接しないように最大合計を見つけるプログラムを作成することです。

問題の説明

配列内で合計シーケンスの2つの数値が隣接しないように、配列からシーケンスの最大合計を見つける必要があります。

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

入力

arr[] = {5, 1, 3, 7, 9, 2, 5}

出力

22

説明

Taking sum sequence from index 0 with alternate elements : 5 + 3 + 9 + 5 = 22
Taking sum sequence from index 1 with alternate elements : 1 + 7 + 2 = 10

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

最後のセットでは、問題を解決するための1つのアプローチを見てきました。ここでは、問題を解決するための動的計画法のアプローチについて学習します。

動的アプローチを使用して問題を解決するには、現在のインデックスまでの最大合計を格納するDP[]配列を作成する必要があります。次に、この動的配列を使用して合計インデックスを見つけます。

現在のDPmaxは、dp [i + 2] +arr[i]とdp[i+1]の最大値です。

例

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

#include <iostream>
using namespace std;
int DP[100];
bool currState[100];
int maxVal(int a, int b){
   if(a > b)
      return a;
      return b;
   }
int calcMaxSumWOAdj(int arr[], int i, int n){
   if (i >= n)
      return 0;
   if (currState[i])
      return DP[i];
   currState[i] = 1;
   DP[i] = maxVal(calcMaxSumWOAdj(arr, i + 1, n), arr[i] + calcMaxSumWOAdj(arr, i + 2, n));
   return DP[i];
}
int main(){
   int arr[] = { 5, 1, 3, 7, 9, 2, 5 };
   int n = sizeof(arr) / sizeof(int);
   cout<<"The maximum sum such that no two elements are adjacent is "<<calcMaxSumWOAdj(arr, 0, n);
   return 0;
}

出力

The maximum sum such that no two elements are adjacent is 22