We have given numbers in form of a triangle, by starting at the top of the triangle and moving to adjacent numbers on the row below, find the maximum total from top to bottom.
Examples :
Input : 3 7 4 2 4 6 8 5 9 3 Output : 23 Explanation : 3 + 7 + 4 + 9 = 23 Input : 8 -4 4 2 2 6 1 1 1 1 Output : 19 Explanation : 8 + 4 + 6 + 1 = 19
Method 1: We can go through the brute force by checking every possible path but that is much time taking so we should try to solve this problem with the help of dynamic programming which reduces the time complexity.
Implementation of Recursive Approach:
C++
// C++ program for // Recursive implementation of // Max sum problem in a triangle #include<bits/stdc++.h> using namespace std; #define N 3 // Function for finding maximum sum int maxPathSum(int tri[][N], int i, int j, int row, int col){ if(j == col ){ return 0; } if(i == row-1 ){ return tri[i][j] ; } return tri[i][j] + max(maxPathSum(tri, i+1, j, row, col), maxPathSum(tri, i+1, j+1, row, col)) ; } /* Driver program to test above functions */int main() { int tri[N][N] = { {1, 0, 0}, {4, 8, 0}, {1, 5, 3} }; cout << maxPathSum(tri, 0, 0, 3, 3); return 0; } |
Java
// Java program for // Recursive implementation of // Max sum problem in a triangle import java.io.*; class GFG { static int N = 3; // Function for finding maximum sum public static int maxPathSum(int tri[][], int i, int j, int row, int col) { if (j == col) { return 0; } if (i == row - 1) { return tri[i][j]; } return tri[i][j] + Math.max( maxPathSum(tri, i + 1, j, row, col), maxPathSum(tri, i + 1, j + 1, row, col)); } /* Driver program to test above functions */ public static void main(String[] args) { int tri[][] = { { 1, 0, 0 }, { 4, 8, 0 }, { 1, 5, 3 } }; System.out.print(maxPathSum(tri, 0, 0, 3, 3)); } } // This code is contributed by Rohit Pradhan |
Python3
# Python program for # Recursive implementation of # Max sum problem in a triangle N = 3 # Function for finding maximum sum def maxPathSum(tri, i, j, row, col): if(j == col ): return 0 if(i == row-1 ): return tri[i][j] return tri[i][j] + max(maxPathSum(tri, i+1, j, row, col), maxPathSum(tri, i+1, j+1, row, col)) # Driver program to test above functions tri = [ [1, 0, 0],[4, 8, 0],[1, 5, 3] ] print(maxPathSum(tri, 0, 0, 3, 3)) # This code is contributed by shinjanpatra |
C#
// C# program for Recursive implementation // of Max sum problem in a triangle using System; public class GFG { static int N = 3; public static int max(int a, int b){ if(a > b) return a; return b; } // Function for finding maximum sum public static int maxPathSum(int[,] tri, int i, int j, int row, int col) { if (j == col) { return 0; } if (i == row - 1) { return tri[i,j]; } return tri[i,j] + max( maxPathSum(tri, i + 1, j, row, col), maxPathSum(tri, i + 1, j + 1, row, col) ); } // Driver program to test above functions public static void Main(string[] args) { int[,] tri = {{ 1, 0, 0 }, { 4, 8, 0 }, { 1, 5, 3 } }; Console.WriteLine(maxPathSum(tri, 0, 0, 3, 3)); } } // This code is contributed by ajaymakavana. |
Javascript
<script> // JavaScript program for // Recursive implementation of // Max sum problem in a triangle const N = 3 // Function for finding maximum sum function maxPathSum(tri, i, j, row, col){ if(j == col ){ return 0; } if(i == row-1 ){ return tri[i][j] ; } return tri[i][j] + Math.max(maxPathSum(tri, i+1, j, row, col), maxPathSum(tri, i+1, j+1, row, col)) ; } /* Driver program to test above functions */let tri = [ [1, 0, 0],[4, 8, 0],[1, 5, 3] ]; document.write(maxPathSum(tri, 0, 0, 3, 3)); // This code is contributed by shinjanpatra </script> |
Output
14
Complexity Analysis:
- Time Complexity: O(2N*N)
- Auxiliary Space: O(N)
If we should left shift every element and put 0 at each empty position to make it a regular matrix, then our problem looks like minimum cost path.
So, after converting our input triangle elements into a regular matrix we should apply the dynamic programming concept to find the maximum path sum.
Method 2: DP Top-Down
Since there are overlapping subproblems, we can avoid the repeated work done in method 1 by storing the min-cost path calculated so far using top-down approach
C++
// C++ program for Dynamic // Programming implementation (Top-Down) of // Max sum problem in a triangle #include<bits/stdc++.h> using namespace std; #define N 3 // Function for finding maximum sum int maxPathSum(int tri[][N], int i, int j, int row, int col, vector<vector<int>> &dp){ if(j == col ){ return 0; } if(i == row-1 ){ return tri[i][j] ; } if(dp[i][j] != -1){ return dp[i][j] ; } return dp[i][j] = tri[i][j] + max(maxPathSum(tri, i+1, j, row, col, dp), maxPathSum(tri, i+1, j+1, row, col, dp)) ; } /* Driver program to test above functions */int main() { int tri[N][N] = { {1, 0, 0}, {4, 8, 0}, {1, 5, 3} }; vector<vector<int>> dp(N, vector<int>(N, -1) ) ; cout << maxPathSum(tri, 0, 0, N, N, dp); return 0; } |
Java
// Java program for Dynamic // Programming implementation (Top-Down) of // Max sum problem in a triangle import java.io.*; import java.util.*; class GFG { // Function for finding maximum sum static int maxPathSum(int[][] tri, int i, int j, int row, int col, int[][] dp) { if (j == col) { return 0; } if (i == row - 1) { return tri[i][j]; } if (dp[i][j] != -1) { return dp[i][j]; } return dp[i][j] = tri[i][j] + Math.max( maxPathSum(tri, i + 1, j, row, col, dp), maxPathSum(tri, i + 1, j + 1, row, col, dp)); } public static void main(String[] args) { int n = 3; int[][] tri = { { 1, 0, 0 }, { 4, 8, 0 }, { 1, 5, 3 } }; int[][] dp = new int[n][n]; for (int[] row : dp) { Arrays.fill(row, -1); } System.out.print(maxPathSum(tri, 0, 0, n, n, dp)); } } // This code is contributed by lokeshmvs21. |
Python3
# C++ program for Dynamic # Programming implementation (Top-Down) of # Max sum problem in a triangle N = 3 # Function for finding maximum sum def maxPathSum(tri, i, j, row, col, dp): if(j == col): return 0 if(i == row-1): return tri[i][j] if(dp[i][j] != -1): return -1 dp[i][j] = tri[i][j] + max(maxPathSum(tri, i+1, j, row, col, dp), maxPathSum(tri, i+1, j+1, row, col, dp)) return dp[i][j] # Driver program to test above functions tri = [ [1, 0, 0], [4, 8, 0], [1, 5, 3] ] dp = [[-1 for i in range(N)]for j in range(N)] print(maxPathSum(tri, 0, 0, N, N, dp)) # This code is contributed by shinjanpatra |
C#
// C# program for Dynamic // Programming implementation (Top-Down) of // Max sum problem in a triangle using System; class GFG { // Function for finding maximum sum static int maxPathSum(int[, ] tri, int i, int j, int row, int col, int[, ] dp) { if (j == col) { return 0; } if (i == row - 1) { return tri[i, j]; } if (dp[i, j] != -1) { return dp[i, j]; } return dp[i, j] = tri[i, j] + Math.Max( maxPathSum(tri, i + 1, j, row, col, dp), maxPathSum(tri, i + 1, j + 1, row, col, dp)); } static void Main() { int[, ] tri = { { 1, 0, 0 }, { 4, 8, 0 }, { 1, 5, 3 } }; int N = 3; int[, ] dp = new int[N, N]; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) dp[i, j] = -1; Console.Write(maxPathSum(tri, 0, 0, N, N, dp)); } } // This code is contributed by garg28harsh. |
Javascript
<script> b// JavaScript program for Dynamic // Programming implementation (Top-Down) of // Max sum problem in a triangle const N = 3 // Function for finding maximum sum function maxPathSum(tri, i, j, row, col, dp){ if(j == col) return 0 if(i == row-1) return tri[i][j] if(dp[i][j] != -1) return -1 dp[i][j] = tri[i][j] + Math.max(maxPathSum(tri, i+1, j, row, col, dp), maxPathSum(tri, i+1, j+1, row, col, dp)) return dp[i][j] } // Driver program to test above functions let tri = [ [1, 0, 0], [4, 8, 0], [1, 5, 3] ] let dp = new Array(N).fill(-1).map(()=>new Array(N).fill(-1)) document.write(maxPathSum(tri, 0, 0, N, N, dp),"</br>") // This code is contributed by shinjanpatra </script> |
Output
14
Complexity Analysis:
- Time Complexity: O(m*n) where m = no of rows and n = no of columns
- Auxiliary Space: O(n2)
Method 3: DP(Bottom – UP)
Since there are overlapping subproblems, we can avoid the repeated work done in method 1 by storing the min-cost path calculated so far using the bottom-up approach thus reducing stack space
C++
// C++ program for Dynamic // Programming implementation of // Max sum problem in a triangle #include<bits/stdc++.h> using namespace std; #define N 3 // Function for finding maximum sum int maxPathSum(int tri[][N], int n, vector<vector<int>> &dp) { // loop for bottom-up calculation for(int j = 0; j < n; j++ ){ dp[n-1][j] = tri[n-1][j] ; } for(int i = n-2; i >= 0; i--){ for(int j = i; j >= 0; j-- ){ dp[i][j] = tri[i][j] + max(dp[i+1][j] , dp[i+1][j+1]) ; } } return dp[0][0] ; } /* Driver program to test above functions */int main() { int tri[N][N] = { {1, 0, 0}, {4, 8, 0}, {1, 5, 3} }; vector<vector<int>> dp(N, vector<int>(N, -1) ) ; cout << maxPathSum(tri, N, dp); return 0; } |
Java
// Java program for Dynamic // Programming implementation of // Max sum problem in a triangle public class Main { // Function for finding maximum sum static int maxPathSum(int[][] tri, int n, int[][] dp) { // loop for bottom-up calculation for (int j = 0; j < n; j++) { dp[n - 1][j] = tri[n - 1][j]; } for (int i = n - 2; i >= 0; i--) { for (int j = i; j >= 0; j--) { dp[i][j] = tri[i][j] + Math.max(dp[i + 1][j], dp[i + 1][j + 1]); } } return dp[0][0]; } public static void main(String[] args) { int N = 3; int[][] tri = { { 1, 0, 0 }, { 4, 8, 0 }, { 1, 5, 3 } }; int[][] dp = new int[N][N]; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { dp[i][j] = -1; } } System.out.println(maxPathSum(tri, N, dp)); } } // This code is contributed by garg28harsh. |
Python3
# Python program for Dynamic # Programming implementation of # Max sum problem in a triangle # Number of rows in the triangle N = 3 # Function for finding maximum sum def maxPathSum(tri, n, dp): # Loop for bottom-up calculation for j in range(n): dp[n-1][j] = tri[n-1][j] for i in range(n-2, -1, -1): for j in range(i, -1, -1): dp[i][j] = tri[i][j] + max(dp[i+1][j], dp[i+1][j+1]) # Return the maximum sum return dp[0][0] # Driver program to test above functions if __name__ == '__main__': # Triangle of numbers tri = [[1, 0, 0], [4, 8, 0], [1, 5, 3]] # Initialize dp array with -1 dp = [[-1 for j in range(N)] for i in range(N)] # Print the maximum sum print(maxPathSum(tri, N, dp)) # This code is contributed by divyansh2212 |
C#
// C# program for Dynamic // Programming implementation of // Max sum problem in a triangle using System; public class GFG { // Function for finding maximum sum static int maxPathSum(int[, ] tri, int n, int[, ] dp) { // loop for bottom-up calculation for (int j = 0; j < n; j++) { dp[n - 1, j] = tri[n - 1, j]; } for (int i = n - 2; i >= 0; i--) { for (int j = i; j >= 0; j--) { dp[i, j] = tri[i, j] + Math.Max(dp[i + 1, j], dp[i + 1, j + 1]); } } return dp[0, 0]; } public static void Main(string[] args) { int N = 3; int[, ] tri = new int[, ] { { 1, 0, 0 }, { 4, 8, 0 }, { 1, 5, 3 } }; int[, ] dp = new int[N, N]; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { dp[i, j] = -1; } } Console.WriteLine(maxPathSum(tri, N, dp)); } } // This code is contributed by karandeep1234 |
Javascript
// Javascript program for Dynamic // Programming implementation of // Max sum problem in a triangle let N = 3 // Function for finding maximum sum function maxPathSum(tri, n, dp) { // loop for bottom-up calculation for(let j = 0; j < n; j++ ){ dp[n-1][j] = tri[n-1][j] ; } for(let i = n-2; i >= 0; i--){ for(let j = i; j >= 0; j-- ){ dp[i][j] = tri[i][j] + Math.max(dp[i+1][j] , dp[i+1][j+1]) ; } } return dp[0][0] ; } /* Driver program to test above functions */let tri = [ [1, 0, 0], [4, 8, 0], [1, 5, 3] ]; let dp = new Array(N); for(let i = 0; i < N; i++) dp[i] = new Array(N).fill(-1); console.log(maxPathSum(tri, N, dp)); // This code is contributed by poojaagarwal2. |
Output
14
Complexity Analysis:
- Time Complexity: O(m*n) where m = no of rows and n = no of columns
- Auxiliary Space: O(n2)
Method 4: Space Optimization (Without Changning input matrix)
We do not need a 2d matrix we only need a 1d array that stores the minimum of the immediate next column and thus we can reduce space
C++
// C++ program for Dynamic // Programming implementation of // Max sum problem in a triangle #include<bits/stdc++.h> using namespace std; #define N 3 // Function for finding maximum sum int maxPathSum(int tri[][N], int n, vector<vector<int>> &dp) { vector<int> front(n, -1) , curr(n, -1) ; for(int j = 0; j < n; j++ ){ front[j] = tri[n-1][j] ; } for(int i = n-2; i >= 0; i--){ for(int j = i; j >= 0; j-- ){ curr[j] = tri[i][j] + max(front[j] , front[j+1]) ; } front = curr ; } return front[0] ; } /* Driver program to test above functions */int main() { int tri[N][N] = { {1, 0, 0}, {4, 8, 0}, {1, 5, 3} }; vector<vector<int>> dp(N, vector<int>(N, -1) ) ; cout << maxPathSum(tri, N, dp); return 0; } |
Java
// Java program for Dynamic // Programming implementation of // Max sum problem in a triangle public class GFG { // Function for finding maximum sum static int maxPathSum(int[][] tri, int n, int[][] dp) { int front[] = new int[n]; int curr[] = new int[n]; for (int j = 0; j < n; j++) { front[j] = tri[n - 1][j]; curr[j] = -1; } for (int i = n - 2; i >= 0; i--) { for (int j = i; j >= 0; j--) { curr[j] = tri[i][j] + Math.max(front[j], front[j + 1]); } front = curr; } return front[0]; } public static void main(String[] args) { int N = 3; int[][] tri = { { 1, 0, 0 }, { 4, 8, 0 }, { 1, 5, 3 } }; int[][] dp = new int[N][N]; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { dp[i][j] = -1; } } System.out.println(maxPathSum(tri, N, dp)); } } // This code is contributed by garg28harsh. |
Python3
# Python program for Dynamic # Programming implementation of # Max sum problem in a triangle N=3 # Function for finding maximum sum def maxPathSum(tri,n,dp): front=[-1]*n curr=[-1]*n for j in range(n): front[j] = tri[n-1][j] for i in range(n-2,-1,-1): for j in range(i,-1,-1): curr[j] = tri[i][j] + max(front[j] ,front[j+1]) front=curr return front[0] # Driver program to test above functions tri=[[1, 0, 0],[4,8,0],[1,5,3]] dp= [[-1 for i in range(N)] for j in range(N)] print(maxPathSum(tri,N,dp)) # This code is contributed by Pushpesh Raj. |
C#
// C# program for Dynamic // Programming implementation of // Max sum problem in a triangle using System; public class GFG { // Function for finding maximum sum static int maxPathSum(int[, ] tri, int n, int[, ] dp) { int[] front = new int[n]; int[] curr = new int[n]; for (int j = 0; j < n; j++) { front[j] = tri[n - 1, j]; curr[j] = -1; } for (int i = n - 2; i >= 0; i--) { for (int j = i; j >= 0; j--) { curr[j] = tri[i, j] + Math.Max(front[j], front[j + 1]); } front = curr; } return front[0]; } public static void Main(string[] args) { int N = 3; int[, ] tri = { { 1, 0, 0 }, { 4, 8, 0 }, { 1, 5, 3 } }; int[, ] dp = new int[N, N]; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { dp[i, j] = -1; } } Console.WriteLine(maxPathSum(tri, N, dp)); } } // This code is contributed by karandeep1234 |
Javascript
// Javascript program for Dynamic // Programming implementation of // Max sum problem in a triangle let N = 3 // Function for finding maximum sum function maxPathSum(tri, n, dp) { let front= new Array(n).fill(-1); let curr=new Array(n).fill(-1); for(let j = 0; j < n; j++ ){ front[j] = tri[n-1][j] ; } for(let i = n-2; i >= 0; i--){ for(let j = i; j >= 0; j-- ){ curr[j] = tri[i][j] + Math.max(front[j] , front[j+1]) ; } front = curr ; } return front[0] ; } /* Driver program to test above functions */let tri = [ [1, 0, 0],[4, 8, 0],[1, 5, 3]]; dp = new Array(N); for(let i = 0; i < N; i++) dp[i] = new Array(N).fill(-1); console.log(maxPathSum(tri, N, dp)); // This code is contributed by ritaagarwal. |
Output
14
Complexity Analysis:
- Time Complexity: O(m*n) where m = no of rows and n = no of columns
- Auxiliary Space: O(n)
Method 5: Space Optimization (Changing input matrix)
Applying, DP in bottom-up manner we should solve our problem as:
Example:
3 7 4 2 4 6 8 5 9 3 Step 1 : 3 0 0 0 7 4 0 0 2 4 6 0 8 5 9 3 Step 2 : 3 0 0 0 7 4 0 0 10 13 15 0 Step 3 : 3 0 0 0 20 19 0 0 Step 4: 23 0 0 0 output : 23
C++
// C++ program for Dynamic // Programming implementation of // Max sum problem in a triangle #include<bits/stdc++.h> using namespace std; #define N 3 // Function for finding maximum sum int maxPathSum(int tri[][N], int m, int n) { // loop for bottom-up calculation for (int i=m-1; i>=0; i--) { for (int j=0; j<=i; j++) { // for each element, check both // elements just below the number // and below right to the number // add the maximum of them to it 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 the top element // which stores the maximum sum return tri[0][0]; } /* Driver program to test above functions */int main() { int tri[N][N] = { {1, 0, 0}, {4, 8, 0}, {1, 5, 3} }; cout << maxPathSum(tri, 2, 2); return 0; } |
Java
// Java Program for Dynamic // Programming implementation of // Max sum problem in a triangle import java.io.*; class GFG { static int N = 3; // Function for finding maximum sum static int maxPathSum(int tri[][], int m, int n) { // loop for bottom-up calculation for (int i = m - 1; i >= 0; i--) { for (int j = 0; j <= i; j++) { // for each element, check both // elements just below the number // and below right to the number // add the maximum of them to it 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 the top element // which stores the maximum sum return tri[0][0]; } /* Driver program to test above functions */ public static void main (String[] args) { int tri[][] = { {1, 0, 0}, {4, 8, 0}, {1, 5, 3} }; System.out.println ( maxPathSum(tri, 2, 2)); } } // This code is contributed by vt_m |
Python3
# Python program for # Dynamic Programming # implementation of Max # sum problem in a # triangle N = 3 # Function for finding maximum sum def maxPathSum(tri, m, n): # loop for bottom-up calculation for i in range(m-1, -1, -1): for j in range(i+1): # for each element, check both # elements just below the number # and below right to the number # add the maximum of them to it 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 the top element # which stores the maximum sum return tri[0][0] # Driver program to test above function tri = [[1, 0, 0], [4, 8, 0], [1, 5, 3]] print(maxPathSum(tri, 2, 2)) # This code is contributed # by Soumen Ghosh. |
C#
// C# Program for Dynamic Programming // implementation of Max sum problem // in a triangle using System; class GFG { // Function for finding maximum sum static int maxPathSum(int [,]tri, int m, int n) { // loop for bottom-up calculation for (int i = m - 1; i >= 0; i--) { for (int j = 0; j <= i; j++) { // for each element, // check both elements // just below the number // and below right to // the number add the // maximum of them to it 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 the top element // which stores the maximum sum return tri[0,0]; } /* Driver program to test above functions */ public static void Main () { int [,]tri = { {1, 0, 0}, {4, 8, 0}, {1, 5, 3} }; Console.Write ( maxPathSum(tri, 2, 2)); } } // This code is contributed by nitin mittal. |
PHP
<?php // PHP program for Dynamic // Programming implementation of // Max sum problem in a triangle // Function for finding // maximum sum function maxPathSum($tri, $m, $n) { // loop for bottom-up // calculation for ( $i = $m - 1; $i >= 0; $i--) { for ($j = 0; $j <= $i; $j++) { // for each element, check // both elements just below // the number and below right // to the number add the maximum // of them to it 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 the top element // which stores the maximum sum return $tri[0][0]; } // Driver Code $tri= array(array(1, 0, 0), array(4, 8, 0), array(1, 5, 3)); echo maxPathSum($tri, 2, 2); // This code is contributed by ajit ?> |
Javascript
<script> // Javascript Program for Dynamic // Programming implementation of // Max sum problem in a triangle let N = 3; // Function for finding maximum sum function maxPathSum(tri, m, n) { // loop for bottom-up calculation for (let i = m - 1; i >= 0; i--) { for (let j = 0; j <= i; j++) { // for each element, check both // elements just below the number // and below right to the number // add the maximum of them to it 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 the top element // which stores the maximum sum return tri[0][0]; } // Driver code let tri = [[1, 0, 0], [4, 8, 0], [1, 5, 3]]; document.write( maxPathSum(tri, 2, 2)); // This code is contributed by susmitakundugoaldanga. </script> |
Output
14
Complexity Analysis:
- Time Complexity: O(m*n) where m = no of rows and n = no of columns
- Auxiliary Space: O(1)
This article is contributed by Shivam Pradhan. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
