2 xn网格中的最大和，这样在C ++中没有两个元素相邻

在这个问题中，我们得到一个大小为2 x n的矩形网格。我们的任务是创建一个程序，以在2 xn的网格中找到最大和，以使C ++中没有两个相邻的元素。

问题描述

为了找到最大和，我们不能选择垂直，水平或对角线与当前元素相邻的元素。

让我们举个例子来了解这个问题，

输入值

rectGrid[2][] =389
411

输出结果

13

说明

所有可能的总和是

如果我们从rectGrid [0] [0]即3开始，那么我们只能加9或1。maxSum为12。

如果我们从rectGrid [1] [0]即4开始，那么我们只能加9或1。maxSum为13。

如果我们从rectGrid [0] [1]即8开始，那么我们就不能添加任何元素。maxSum为8。

如果我们从rectGrid [1] [1]即1开始，那么我们就不能添加任何元素。maxSum为1。

如果我们从rectGrid [0] [2]即9开始，那么我们只能加3或4。maxSum为13。

如果我们从rectGrid [1] [2]即1开始，那么我们只能加3或4。maxSum为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