資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究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
更新於: 2020年10月15日
285 次檢視
廣告