C ++中不允许从三个数组中获取最大和，以至于无法连续从中选择元素

在此问题中，我们给三个数组arr1 []，arr2 []和arr3 []均大小为N。我们的任务是创建一个程序，以从三个数组中查找最大和，以便不从中连续选取元素在C ++中允许。

问题描述

通过选择N个元素，我们将找到最大和。可以从数组的第i个元素中选择和，即第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

解决方法

为了解决该问题，我们将使用动态编程方法，我们还需要将总和存储到索引中，以避免额外的计算。我们将创建一个二维矩阵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