C++ 中求 2 x n 网格中任意两个元素不相邻的最大和
c++server side programmingprogramming
本题中，给定一个 2 x n 的矩形网格。我们的任务是编写一个程序，用 C++ 语言在 2 x n 的网格中求出最大和，使得任意两个元素都不相邻。
问题描述
为了求最大和，我们不能选择与当前元素相邻的元素，无论是垂直、水平还是对角线方向。
让我们举个例子来理解这个问题:
输入
rectGrid[2][] =389 411
输出
13
解释
所有可能的和都是
如果我们从 rectGrid[0][0] 即 3 开始，那么我们只能加 9 或 1。最大和是12.
如果从 rectGrid[1][0] 即 4 开始，那么我们只能添加 9 或 1。最大和为 13。
如果从 rectGrid[0][1] 即 8 开始，那么我们不能添加任何元素。最大和为 8。
如果从 rectGrid[1][1] 即 1 开始，那么我们不能添加任何元素。最大和为 1。
如果我们从 rectGrid[0][2] 开始，即 9，那么我们只能加 3 或 4。最大和为 13。
如果我们从 rectGrid[1][2] 开始，即 1，那么我们只能加 3 或 4。最大和为 5。
总和为 13。
解决方法
这个问题类似于我们在上一篇文章中看到的最大和问题，即没有两个元素相邻。不同之处在于这里的数组是二维的，并且相邻元素的条件不同。因此，我们将使用行和列的条件来考虑最大元素。由于每列有两行，我们将最大限度地考虑交替元素。
示例
用于说明解决方案工作原理的程序
#include<iostream>
using namespace std;
int findMax(int a, int b){
if(a > b)
return a;
return b;
}
int calcMaxSum(int rectGrid[2][20], int N){
int currectSum = 0;
int nextSum = 0;
int altSum;
for (int i = 0; i<N; i++ ){
altSum = findMax(nextSum, currectSum);
currectSum = nextSum + findMax(rectGrid[0][i], rectGrid[1][i]);
nextSum = altSum;
}
int maxSum = findMax(nextSum, currectSum);
return maxSum;
}
int main(){
int rectGrid[2][20] = {{3, 8, 9, 5},
{4, 1, 2, 7}};
int N = 4;
cout<<"The maximum sum in a 2 x "<<N<<" grid such that no two elements are adjacent is "<<calcMaxSum(rectGrid, N);
return 0;
}
输出
The maximum sum in a 2 x 4 grid such that no two elements are adjacent is 15
