最大子序列总和，以使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 给外婆敬酒祝福语简短