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 matrix ; 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 code
using System ; class MaxSumPath { static int maxSum ( int [ , ] mat , int n ) { if ( n == 1 ) return mat [ 0 , 0 ] ; int [ , ] dp = new int [ n , n ] ; int maxSum = int . MinValue , 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 . MinValue ; 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 ; } public static void Main ( ) { int [ , ] mat = { { 5 , 6 , 1 , 7 } , { - 2 , 10 , 8 , - 1 } , { 3 , - 7 , - 9 , 11 } , { 12 , - 4 , 2 , 6 } } ; int n = 4 ; Console . WriteLine ( " Maximum ▁ Sum ▁ = ▁ " + maxSum ( mat , n ) ) ; } }