C++ 中求任意两个元素不相邻的最大和
c++server side programmingprogramming
本题中，给定一个数组 arr[]。我们的任务是编写一个程序，用 C++ 语言求出最大和，使得任意两个元素都不相邻。
问题描述
我们需要从数组中找到一个序列的最大和，使得和序列中任意两个数字都不相邻。
让我们举个例子来理解这个问题:
输入
arr[] = {5, 1, 3, 7, 9, 2, 5}
输出
22
解释
从索引 0 开始，使用交替元素对序列求和:5 + 3 + 9 + 5 = 22 从索引 1 开始，使用交替元素对序列求和: 1 + 7 + 2 = 10
解决方法
为了解决这个问题，我们将简单地循环遍历数组的所有元素并维护两个和:sumVar1 和 sumVar2。sumVar1 将包含当前元素的和，而 sumVar2 将包含不包含当前元素的和。
每次迭代时，我们将 sumVar2 更新为 max(sumVar1, sumVar2)。然后更新 sumVar1。在循环结束时，sumVar2 将给出所需的和。
示例
用于说明我们解决方案工作原理的程序:
#include<iostream>
using namespace std;
int findmaximum(int a, int b){
if(a > b)
return a;
return b;
}
int findMaxSumWOAdjecent(int arr[], int N){
int maxSum1 = arr[0];
int maxSum2 = 0;
int temp;
for (int i = 1; i < N; i++) {
temp = findmaximum(maxSum1, maxSum2);
maxSum1 = maxSum2 + arr[i];
maxSum2 = temp;
}
return (findmaximum(maxSum1, maxSum2));
}
int main(){
int arr[] = {5, 1, 3, 7, 9, 2, 5};
int N = sizeof(arr) / sizeof(arr[0]);
cout<<"没有两个元素相邻的最大和是 "<<findMaxSumWOAdjecent(arr, N);
return 0;
}
输出
没有两个元素相邻的最大和是 22
