C++で2つの要素が隣接しないような循環配列の最大合計

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

問題の説明

循環配列の場合、隣接する要素を取得できないように、配列の要素の最大合計を見つける必要があります。つまり、代替要素を取得する必要があります。

循環アレイ は、配列の最後の要素が最初の要素に接続されている特殊なタイプの配列です。

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

入力

cirArr[] = {4, 1, 5, 3, 2}

出力

9

説明

最大合計循環サブシーケンスは[4、5、2]です。合計=9

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

この問題の解決策は、動的計画法を使用して最大合計を見つけることです。合計は、循環配列を2つの配列として扱うことで抽出できます。1つはインデックス0からN-2まで、もう1つはインデックス1からn-1までです。これにより、2つのアレイが作成され、これらのアレイからの合計の最大合計が結果になります。

例

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

#include <iostream>
using namespace std;
int calcMaxVal(int a, int b){
   if(a > b)
      return a;
   return b;
}
int calcMaxSumSubSeq(int cirArr[], int start, int end, int n) {
   int DP[n];
   int maxSum = 0;
   for (int i = start; i < (end + 1); i++) {
      DP[i] = cirArr[i];
      if (maxSum < cirArr[i])
         maxSum = cirArr[i];
   }
   for (int i = (start + 2); i < (end + 1); i++) {
      for (int j = 0; j < i - 1; j++) {
         if (DP[i] < DP[j] + cirArr[i]) {
            DP[i] = DP[j] + cirArr[i];
            if (maxSum < DP[i])
               maxSum = DP[i];
         }
      }
   }
   return maxSum;
}
int findMaxSum(int cirArr[], int n){
   int maxSumArray1 = calcMaxSumSubSeq(cirArr, 0, (n-2), n);
   int maxSumArray2 = calcMaxSumSubSeq(cirArr, 1, (n-1), n);
   int maxSum = calcMaxVal(maxSumArray1, maxSumArray2);
   return maxSum;
}
int main(){
   int cirArr[] = {4, 1, 5, 3, 2};
   int n = sizeof(cirArr)/sizeof(cirArr[0]);
   cout<<"The maximum sum in circular array such that no two elements are adjacent is "<<findMaxSum(cirArr, n);
   return 0;
}

出力

The maximum sum in circular array such that no two elements are adjacent is 9