最大子序列总和，以使C ++程序中没有三个连续子序列

在这个问题中，我们得到了一个由n个正整数组成的数组arr []。我们的任务是创建一个程序来查找最大子序列和，以使三个子序列都不连续。

问题描述-在这里，我们需要找到从数组创建的序列的总和，以确保没有三个连续的元素。

数组的连续元素是遵循相同索引顺序的那些元素。

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]

然后，不能直接考虑要考虑的第三个值。对于总和，我们将检查当前三个条件，如果考虑到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