Maximum sum path in a matrix from top to bottom | C ++ implementation to find the maximum sum path in a matrix ; function to find the maximum sum path in a matric ; if there is a single element only ; dp [ ] [ ] matrix to store the results of each iteration ; base case , copying elements of last row ; building up the dp [ ] [ ] matrix from bottom to the top row ; finding the maximum diagonal element in the ( i + 1 ) th row if that cell exists ; adding that ' max ' element to the mat [ i ] [ j ] element ; finding the maximum value from the first row of dp [ ] [ ] ; required maximum sum ; Driver program to test above
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define SIZE  10 NEW_LINE 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 ; }