C ++では、同じ要素から連続して要素を選択できないように、3つの配列からの最大合計

この問題では、すべてサイズNの3つの配列arr1 []、arr2 []、およびarr3 []が与えられます。私たちのタスクは、3つの配列から最大合計を見つけて、同じ要素から連続して要素を選択しないようにするプログラムを作成することです。 C++で許可されています。

問題の説明

N個の要素を選択することで最大の合計を求めます。 i =番目の要素は、配列のi番目の要素からの合計から選択できます。つまり、i番目の合計はarr1 [i] / arr2 [i] /arr3[i]からのものです。また、同じ配列から選択できる2つの連続した要素を選択することはできないことに注意してください。

問題を理解するために例を見てみましょう

Inout

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番目の配列を使用します。現在の要素を再帰的に見つけてから、他の2つの配列から次の要素の合計を呼び出します。

例

ソリューションの動作を説明するプログラム

#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