C++에서 두 요소가 인접하지 않도록 원형 배열의 최대 합계

이 문제에서는 원형 배열 cirArr[]이 제공됩니다. 우리의 임무는 C++에서 두 요소가 인접하지 않도록 원형 배열에서 최대 합을 찾는 프로그램을 만드는 것입니다.

문제 설명

원형 배열의 경우 인접 요소를 사용할 수 없도록 배열 요소의 최대 합을 찾아야 합니다. 즉, 대체 요소를 가져와야 합니다.

원형 배열 배열의 마지막 요소가 첫 번째 요소에 연결되는 특수한 유형의 배열입니다.

문제를 이해하기 위해 예를 들어 보겠습니다.

입력

cirArr[] = {4, 1, 5, 3, 2}

출력

9

설명

최대 합 순환 부분 수열은 [4, 5, 2]입니다. 합계 =9

솔루션 접근 방식

이 문제에 대한 해결책은 최대 합을 찾기 위해 동적 계획법 접근 방식을 사용하는 것입니다. 합계는 원형 배열을 두 개의 배열로 처리하여 추출할 수 있습니다. 하나는 인덱스 0에서 N-2까지이고 다른 하나는 인덱스 1에서 n-1까지입니다. 이렇게 하면 두 개의 배열이 생성되고 이 배열의 합을 합한 최대값이 결과가 됩니다.

예시

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

#include <iostream>
using namespace std;
int calcMaxVal(int a, int b){
   if(a > b)
      return a;
   return b;
}
int calcMaxSumSubSeq(int cirArr[], int start, int end, int n) {
   int DP[n];
   int maxSum = 0;
   for (int i = start; i < (end + 1); i++) {
      DP[i] = cirArr[i];
      if (maxSum < cirArr[i])
         maxSum = cirArr[i];
   }
   for (int i = (start + 2); i < (end + 1); i++) {
      for (int j = 0; j < i - 1; j++) {
         if (DP[i] < DP[j] + cirArr[i]) {
            DP[i] = DP[j] + cirArr[i];
            if (maxSum < DP[i])
               maxSum = DP[i];
         }
      }
   }
   return maxSum;
}
int findMaxSum(int cirArr[], int n){
   int maxSumArray1 = calcMaxSumSubSeq(cirArr, 0, (n-2), n);
   int maxSumArray2 = calcMaxSumSubSeq(cirArr, 1, (n-1), n);
   int maxSum = calcMaxVal(maxSumArray1, maxSumArray2);
   return maxSum;
}
int main(){
   int cirArr[] = {4, 1, 5, 3, 2};
   int n = sizeof(cirArr)/sizeof(cirArr[0]);
   cout<<"The maximum sum in circular array such that no two elements are adjacent is "<<findMaxSum(cirArr, n);
   return 0;
}

출력

The maximum sum in circular array such that no two elements are adjacent is 9