C++ 中 2 x n 网格的最大和，且任意两个元素不相邻

在这个问题中，我们给定了一个大小为 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

Ayush Gupta

更新于: 2020年10月15日

285 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习