数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++中从三个数组中获取最大和，但不能连续选择来自同一数组的元素
在这个问题中，我们得到三个大小为N的数组arr1[]、arr2[]和arr3[]。我们的任务是编写一个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
更新于：2020年10月15日
271 次浏览
广告