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