Maximum sum path in a matrix from top to bottom in C++ Program
https://www.tutorialspoint.com/maximum-sum-path-in-a-matrix-from-top-to-bottom-in-cplusplus-program
-
10-09-2020 - |
Вопрос
In this tutorial, we will be discussing a program to find maximum sum path in a matrix from top to bottom.
For this we will be provided with a matrix of N*N size. Our task is to find the maximum sum route from top row to bottom row while moving to diagonally higher cell.
Example
#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; }
Output
Maximum Sum = 28
Не связан с Tutorialspoint