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