두 요소가 인접하지 않도록 하는 최대 합계 C++ 프로그램의 대체 방법

이 문제에서는 양수 값으로 구성된 n 크기의 배열 arr[]이 제공됩니다. 우리의 임무는 배열의 두 개의 연속 요소가 없는 방식으로 최대 부분 수열 합을 찾는 프로그램을 만드는 것입니다.

문제 설명 − 배열의 요소를 포함하지만 배열의 인접한 두 요소를 고려할 수 없는 하위 배열의 합을 찾아야 합니다.

예

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

입력

arr[] = {5, 2, 1, 9, 6}

출력

설명 -

Subarray sum are :
{5, 1, 6}, sum = 5 + 1 + 6 = 12
{2, 9}, sum = 2 + 9 = 11

해결 방법

여기서 우리는 동적 프로그래밍 접근 방식을 사용하는 문제에 대한 대체 솔루션을 갖게 될 것입니다. 이 접근 방식에서 우리는 주어진 조건을 만족하는 부분 시퀀스를 찾고 최대값을 출력할 것입니다. 생성된 부분 시퀀스의 최대 부분을 저장하는 배열 maxSumDP[n]을 생성할 것입니다. 요소 maxSumDP[i]는 인덱스 i에서 n-1까지 요소를 취하여 생성된 하위 시퀀스의 최대 합을 저장합니다. 이를 위해 배열 arr[i]의 현재 요소를 고려할 수 있습니다. 즉, maxSumDP[i] =arr[i] + maxSumDP[i+2]. 또는 배열 arr[i]의 현재 요소, 즉 maxSumDP[i] =maxSumDP[i+2]를 고려하지 마십시오.

알고리즘

초기화 -

maxSumDP[]

2단계 -

initialize the values of maxSumDP[n−1] and maxSumDP[n−2].
maxSumDP[n−1] = arr[n−1] and maxSumDP[n−2] = max(arr[n−1], arr[n−2]).

2단계 -

loop for i −> n−2 to 0

1.2단계 -

initialize the value of maxSumDP[i],
maxSumDP[i] = maximum of (arr[i] + maxSumDP[i + 2],
maxSumDP[i + 1])

3단계 -

Return maxSumDP[0] which is the maximum sum sequence sum.

예

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

#include <iostream>
using namespace std;
int retMaxVal(int a, int b){
   if(a > b)
   return a;
   return b;
}
int calcMaxSum(int arr[], int n){
   int maxSumDP[n];
   maxSumDP[n−1] = arr[n−1];
   maxSumDP[n−2] = max(arr[n−1], arr[n−2]);
   for (int i = n − 2; i >= 0; i−−) {
      maxSumDP[i] = retMaxVal(arr[i] + maxSumDP[i + 2],
      maxSumDP[i + 1]);
   }
   return maxSumDP[0];
}
int main() {
   int arr[] = { 5, 2 , 1, 9, 6 };
   int n = sizeof(arr) / sizeof(int);
   cout<<"The maximum subsequence sum in such a way that no two consecutive elements of the array is "<<calcMaxSum(arr, n);
   return 0;
}

출력

The maximum subsequence sum in such a way that no two consecutive
elements of the array is 14