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

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

この問題を解決するには、配列のすべての要素をループして、2つの合計を維持します。 sumVar1とsumVar2、sumVar1には現在の要素を含む合計が含まれ、sumVar2には現在の要素を含まない合計が含まれます。

反復ごとに、sumVar2をmax（sumVar1、sumVar2）として更新します。次に、sumVar1を更新します。ループの終わりに、sumVar2は必要な合計を返します。

例

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

#include<iostream>
using namespace std;
int findmaximum(int a, int b){
   if(a > b)
      return a;
      return b;
}
int findMaxSumWOAdjecent(int arr[], int N){
   int maxSum1 = arr[0];
   int maxSum2 = 0;
   int temp;
   for (int i = 1; i < N; i++) {
      temp = findmaximum(maxSum1, maxSum2);
      maxSum1 = maxSum2 + arr[i];
      maxSum2 = temp;
   }
   return (findmaximum(maxSum1, maxSum2));
}
int main(){
   int arr[] = {5, 1, 3, 7, 9, 2, 5};
   int N = sizeof(arr) / sizeof(arr[0]);
   cout<<"The maximum sum such that no two elements are adjacent is "<<findMaxSumWOAdjecent(arr, N);
   return 0;
}

出力

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