C ++中没有两个相邻元素的最大和

在这个问题中,我们得到了一个数组arr []。我们的任务是创建一个程序来查找最大和,以使C ++中没有两个相邻的元素。

问题描述

我们需要从数组中找到序列的最大和,以使总和序列中没有2个数字在数组中相邻。

让我们举个例子来了解这个问题,

输入值

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将包含当前元素的sum,sumVar2将包含不包含当前元素的sum。

每次迭代时,我们会将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