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 婆婆高寿祝福语大全简短