C++에서는 동일한 요소에서 연속적으로 요소를 선택하는 것이 허용되지 않는 세 가지 배열의 최대 합계

이 문제에서는 크기가 N인 3개의 배열 arr1[], arr2[], arr3[]이 제공됩니다. 우리의 임무는 동일한 요소에서 연속적으로 요소를 선택하지 않도록 3개의 배열에서 최대 합을 찾는 프로그램을 만드는 것입니다. C++에서 허용됩니다.

문제 설명

N개의 요소를 선택하여 최대 합을 찾습니다. i=th 요소는 배열의 i번째 요소의 합에서 선택할 수 있습니다. 즉, i번째 합은 arr1[i]/ arr2[i]/ arr3[i]입니다. 또한 동일한 배열에서 선택할 수 있는 두 개의 연속 요소를 선택할 수 없다는 점에 유의하십시오.

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

인아웃

arr1[] = {5, 8, 9, 20},
arr2[] = {7, 12, 1, 10},
arr3[] = {8, 9, 10, 11}
N = 4

출력

50

설명

i =1인 경우 arr3의 합계에 대해 8을 고려합니다. i =2인 경우 arr2의 합계에 대해 12를 고려합니다. i =3의 경우 arr3의 합계에 대해 10을 고려합니다. i =4인 경우 arr1의 합계에 대해 20을 고려합니다. 합계 =8 + 12 + 10 + 20 =50

해결 방법

문제를 해결하기 위해 동적 프로그래밍 방식을 사용할 것이며 추가 계산을 피하기 위해 인덱스까지 합계를 기억해야 합니다. 2차원 행렬 DP[][]를 생성합니다. 인덱스 i,j에 있는 요소는 i번째 인덱스까지 j번째 배열을 사용하는 요소의 합이 됩니다. 현재 요소를 재귀적으로 찾은 다음 다른 두 배열에서 다음 요소의 합을 호출합니다.

예

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

#include <bits/stdc++.h>
using namespace std;
const int N = 3;
int findMaxVal(int a, int b){
   if(a > b)
      return a;
      return b;
}
int FindMaximumSum(int index, int arrNo, int arr1[], int arr2[], int arr3[], int n, int DP[][N]){
   if (index == n)
      return 0;
   if (DP[index][arrNo] != -1)
      return DP[index][arrNo];
      int maxVal = -1;
   if (arrNo == 0){
      maxVal = findMaxVal(maxVal, arr2[index] + FindMaximumSum(index + 1, 1, arr1, arr2, arr3, n, DP));
      maxVal = findMaxVal(maxVal, arr3[index] + FindMaximumSum(index + 1, 2, arr1, arr2, arr3, n, DP));
   }
   else if (arrNo == 1){
      maxVal = findMaxVal(maxVal, arr1[index] + FindMaximumSum(index + 1, 0, arr1, arr2, arr3, n, DP));
      maxVal = findMaxVal(maxVal, arr3[index] + FindMaximumSum(index + 1, 2, arr1, arr2, arr3, n, DP));
   }
   else if (arrNo == 2){
      maxVal = findMaxVal(maxVal, arr1[index] + FindMaximumSum(index + 1, 1, arr1, arr2, arr3, n, DP));
      maxVal = findMaxVal(maxVal, arr2[index] + FindMaximumSum(index + 1, 0, arr1, arr2, arr3, n, DP));
   }
   return DP[index][arrNo] = maxVal;
}
int main(){
   int arr1[] = { 5, 8, 9, 20 };
   int arr2[] = { 7, 12, 1, 10 };
   int arr3[] = { 8, 9, 10, 11 };
   int n = sizeof(arr1) / sizeof(arr1[0]);
   int DP[n][N];
   memset(DP, -1, sizeof DP);
   int val1 = FindMaximumSum(0, 0, arr1, arr2, arr3, n, DP);
   int val2 = FindMaximumSum(0, 1, arr1, arr2, arr3, n, DP);
   int val3 = FindMaximumSum(0, 2, arr1, arr2, arr3, n, DP);
   cout<<"The maximum sum from three arrays such that picking elements consecutively from same is not allowed is "<<findMaxVal(val1, findMaxVal(val2, val3));
   return 0;
}

출력

The maximum sum from three arrays such that picking elements consecutively from same is not allowed is 50