数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究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
更新于: 2020年12月9日
117 次查看
广告