Maximum path sum in a triangle . | C # Program for Dynamic Programming implementation of Max sum problem in a triangle ; Function for finding maximum sum ; loop for bottom - up calculation ; for each element , check both elements just below the number and below right to the number add the maximum of them to it ; return the top element which stores the maximum sum ; Driver program to test above functions
using System ; class GFG { static int maxPathSum ( int [ , ] tri , int m , int n ) { for ( int i = m - 1 ; i >= 0 ; i -- ) { for ( int j = 0 ; j <= i ; j ++ ) { if ( tri [ i + 1 , j ] > tri [ i + 1 , j + 1 ] ) tri [ i , j ] += tri [ i + 1 , j ] ; else tri [ i , j ] += tri [ i + 1 , j + 1 ] ; } } return tri [ 0 , 0 ] ; } public static void Main ( ) { int [ , ] tri = { { 1 , 0 , 0 } , { 4 , 8 , 0 } , { 1 , 5 , 3 } } ; Console . Write ( maxPathSum ( tri , 2 , 2 ) ) ; } }