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
热门推荐
10 香港老妈结婚祝福语简短
11 毕业立体贺卡祝福语简短
12 简短新年年会祝福语
13 评论小品祝福语大全简短
14 恭喜师兄结婚祝福语简短
15 员工集体辞职祝福语简短
16 高中新生祝福语 简短
17 装修祝福语男生搞笑简短
18 生日开业蛋糕祝福语简短