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 官宣新年祝福语简短