두 요소가 인접하지 않도록 하는 최대 합계 - C++에서 2를 설정합니다.

이 문제에서는 배열 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

솔루션 접근 방식

마지막 세트에서 우리는 문제를 해결하기 위한 한 가지 접근 방식을 보았습니다. 여기에서 우리는 문제를 해결하기 위한 동적 프로그래밍 접근 방식에 대해 배울 것입니다.

Dynamic Approach를 사용하여 문제를 해결하려면 현재 인덱스까지 해당 최대 합계를 저장하는 DP[] 배열을 만들어야 합니다. 그런 다음 이 동적 배열을 사용하여 합계 인덱스를 찾습니다.

현재 DP 최대값은 dp[i+2]+ arr[i] 및 dp[i+1]의 최대값입니다.

예시

솔루션의 작동을 설명하는 프로그램,

#include <iostream>
using namespace std;
int DP[100];
bool currState[100];
int maxVal(int a, int b){
   if(a > b)
      return a;
      return b;
   }
int calcMaxSumWOAdj(int arr[], int i, int n){
   if (i >= n)
      return 0;
   if (currState[i])
      return DP[i];
   currState[i] = 1;
   DP[i] = maxVal(calcMaxSumWOAdj(arr, i + 1, n), arr[i] + calcMaxSumWOAdj(arr, i + 2, n));
   return DP[i];
}
int main(){
   int arr[] = { 5, 1, 3, 7, 9, 2, 5 };
   int n = sizeof(arr) / sizeof(int);
   cout<<"The maximum sum such that no two elements are adjacent is "<<calcMaxSumWOAdj(arr, 0, n);
   return 0;
}

출력

The maximum sum such that no two elements are adjacent is 22