C++プログラムで3つが連続しないような最大サブシーケンスの合計

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

問題の説明 −ここでは、3つの連続する要素がないように、配列から作成されたシーケンスの合計を見つける必要があります。

の連続する要素 配列は、同じインデックスの順序に従った要素です。

arr[0], arr[1], arr[2], …

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

入力

arr[] = {5, 9, 12, 15}

出力

32

説明

Sum = 5 + 12 + 15 = 32

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

この問題の簡単な解決策は、現在のインデックスまで合計を格納するための補助配列を作成することです。次に、合計を見つけて、連続する合計をチェックすることにより、インデックスまでの合計をチェックします。

For the first two sum values,
sumVal[0] = arr[0]
sumVal[1] = arr[0] + arr[1]

その場合、考慮される3番目の値を直接考慮することはできません。そして、合計を考慮するために、現在の3つの条件をチェックします。arr[i]を考慮する場合は、合計値を増やし、arr[i-1]またはarr[i-2]を除外します。それ以外の場合はarr[iを考慮しません。 ]、合計は同じままです。

sum[i] = max(sum[i−3] + arr[i−1] + arr[i], sum[i−2] + arr[i], sum[i−1])

例

ソリューションの実装を示すプログラム

#include <iostream>
using namespace std;
int findMaxSubSeqSum(int arr[], int n) {
   int maxSumArr[n];
   maxSumArr[0] = arr[0];
   maxSumArr[1] = arr[0] + arr[1];
   maxSumArr[2] = max(maxSumArr[1], max(arr[1] + arr[2], arr[0] +
   arr[2]));
   for (int i = 3; i < n; i++){
      int sum1 = maxSumArr[i − 2] + arr[i];
      int sum2 = arr[i] + arr[i − 1] + maxSumArr[i − 3];
      maxSumArr[i] = max(max(maxSumArr[i − 1], sum1), sum2);
   }
   return maxSumArr[n − 1];
}
int main() {
   int arr[] = { 5, 9, 12, 15 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"The maximum subsequence sum such that no three are
   consecutive is "<<findMaxSubSeqSum(arr, n);
   return 0;
}

出力

The maximum subsequence sum such that no three are consecutive is 32