在这个问题中,我们得到一个大小为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