最大子序列总和，以使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
热门推荐
10 八一幼儿祝福语大全简短
11 公司乔迁食堂祝福语简短
12 婚礼结束聚餐祝福语简短
13 儿媳买车妈妈祝福语简短
14 毕业送礼老师祝福语简短
15 同事辞职正常祝福语简短
16 恭贺新婚文案祝福语简短
17 金店立秋祝福语简短英文
18 婆婆高寿祝福语大全简短