資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究從上到下求解 C++ 中矩陣中的最大和路徑的程式
在本文件中，我們將討論一個程式，該程式用於查詢從上到下在矩陣中的最大和路徑。
為此，我們將獲得 N*N 大小的矩陣。我們的任務是找到從頂部行到底部行且同時移動到對角線上方單元格時的最大和路徑。
示例
#include <bits/stdc++.h>
using namespace std;
#define SIZE 10
//finding maximum sum path
int maxSum(int mat[SIZE][SIZE], int n) {
if (n == 1)
return mat[0][0];
int dp[n][n];
int maxSum = INT_MIN, max;
for (int j = 0; j < n; j++)
dp[n - 1][j] = mat[n - 1][j];
for (int i = n - 2; i >= 0; i--) {
for (int j = 0; j < n; j++) {
max = INT_MIN;
if (((j - 1) >= 0) && (max < dp[i + 1][j - 1])) max = dp[i + 1][j - 1];
if (((j + 1) < n) && (max < dp[i + 1][j + 1])) max = dp[i + 1][j + 1];
dp[i][j] = mat[i][j] + max;
}
}
for (int j = 0; j < n; j++)
if (maxSum < dp[0][j])
maxSum = dp[0][j];
return maxSum;
}
int main() {
int mat[SIZE][SIZE] = {
{ 5, 6, 1, 7 },
{ -2, 10, 8, -1 },
{ 3, -7, -9, 11 },
{ 12, -4, 2, 6 }
};
int n = 4;
cout << "Maximum Sum = " << maxSum(mat, n);
return 0;
}輸出
Maximum Sum = 28
更新於： 2020-09-09
230 次檢視
廣告