資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++矩陣最大路徑和
在這個問題中，我們給定一個大小為M*N的二維矩陣。我們的任務是建立一個程式來查詢矩陣中的最大路徑和。
這裡，矩陣中的最大路徑和定義為從第一行到最後一行所有元素的總和。允許的遍歷路徑移動是向下移動和對角移動。起點和終點可以分別是矩陣的第一行和最後行的任何元素。
讓我們來看一個例子來理解這個問題
輸入 −
matrix [][] = 3 5 9 1 7 2 4 8 6
輸出 − 24
解釋 − 最大路徑將是 9 → 7 → 8。
為了解決這個問題，我們將從陣列頂部開始，找到第一行中最大的元素，並將其儲存到maxSum中。然後遍歷矩陣並查詢路徑中出現的最大值。如果新值更大，則更新maxSum，否則不更新。一旦遍歷完整個矩陣並建立了路徑，就返回maxSum。
示例
查詢矩陣中最大路徑和的程式 −
#include <iostream>
#define N 3
#define M 3
using namespace std;
int maxPathSum(int mat[][M]){
for (int i = 1; i < N; i++) {
for (int j = 0; j < M; j++) {
if (j > 0 && j < M - 1)
mat[i][j] += max(mat[i - 1][j], max(mat[i - 1][j - 1],mat[i - 1][j + 1]));
else if (j > 0)
mat[i][j] += max(mat[i - 1][j],
mat[i - 1][j - 1]);
else if (j < M - 1)
mat[i][j] += max(mat[i - 1][j],
mat[i - 1][j + 1]);
}
}
int maxSum = mat[N-1][0];
for (int j = 1; j < M; j++)
maxSum = max(mat[N-1][j], maxSum);
return maxSum;
}
int main(){
int matrix[N][M] = {
{3, 5, 9 },
{1, 7, 2},
{4, 8, 6}};
cout<<"The maximum path sum of matrix is : "<<maxPathSum(matrix);
return 0;
}輸出
The maximum path sum of matrix is : 24
更新於: 2020年6月3日
685 次瀏覽
廣告