C++で2つの要素が隣接しないような2xnグリッドの最大合計

この問題では、サイズ2xnの長方形グリッドが与えられます。私たちのタスクは、C++で2つの要素が隣接しないように2xnグリッドで最大合計を見つけるプログラムを作成することです。

問題の説明

最大の合計を見つけるために、現在の要素に隣接する要素を垂直、水平、または斜めに選択することはできません。

問題を理解するために例を見てみましょう

入力

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です。

ソリューションアプローチ

この問題は最大合計に似ているため、前回の投稿で見たように2つの要素が隣接していません。違いは、ここでは2Dの配列と、隣接する要素の条件です。したがって、行と列の両方の条件を使用して最大要素を検討します。各列には2つの行があるため、代替要素を最大限に考慮します。

例

ソリューションの動作を説明するプログラム

#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