数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++中求最大和，且任意两个元素不相邻
在这个问题中，我们给定一个数组 arr[]。我们的任务是编写一个 C++ 程序来查找最大和，条件是数组中任意两个元素不相邻。
问题描述
我们需要从数组中找到一个序列的最大和，条件是该序列中任意两个数字在数组中不相邻。
让我们来看一个例子来理解这个问题：
输入
arr[] = {5, 1, 3, 7, 9, 2, 5}输出
22
解释
Taking sum sequence from index 0 with alternate elements : 5 + 3 + 9 + 5 = 22 Taking sum sequence from index 1 with alternate elements : 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<<"The maximum sum such that no two elements are adjacent is "<<findMaxSumWOAdjecent(arr, N);
return 0;
}输出
The maximum sum such that no two elements are adjacent is 22
更新于：2020年10月15日
189 次浏览
广告