Given numbers in form of an Inverted triangle. By starting at the bottom of the triangle and moving to adjacent numbers on the row above, find the maximum total from bottom to top.
Examples:
Input : 1 5 3
4 8
1
Output : 14
Input : 8 5 9 3
2 4 6
7 4
3
Output : 23
Method 1: Recursion
In the previous article we saw an approach of the problem where the triangle is non-inverted.
Here also we will use the same approach to find the solution of the problem as discussed in previous article.
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.
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 sumint maxPathSum(int tri[][N], int i, int j, int row, int col){ if(j == col ){ return INT_MIN; } if(i == 0 ){ 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, 5, 3 }, { 4, 8, 0 }, { 1, 0, 0 } }; cout << maxPathSum(tri, 2, 0, 2, 2); return 0;} |
Java
// Java program for// Recursive implementation of// Max sum problem in a triangleimport java.util.*;class GFG { // Function for finding maximum sum static int maxPathSum(int[][] tri, int i, int j, int row, int col) { if (j == col) { return Integer.MIN_VALUE; } if (i == 0) { 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 = new int[][] { { 1, 5, 3 }, { 4, 8, 0 }, { 1, 0, 0 } }; System.out.println(maxPathSum(tri, 2, 0, 2, 2)); }}// This code is contributed by phasing17 |
Python3
# Python3 program for# Recursive implementation of# Max sum problem in a triangle N = 3# Function for finding maximum sumdef maxPathSum(tri, i, j, row, col): if(j == col ): return -100000; if(i == 0 ): 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, 5, 3 ], [ 4, 8, 0 ], [ 1, 0, 0 ]];print(maxPathSum(tri, 2, 0, 2, 2));# This code is contributed by phasing17 |
C#
// C# program for// Recursive implementation of// Max sum problem in a triangleusing System;using System.Collections.Generic;class GFG { // Function for finding maximum sum static int maxPathSum(int[, ] tri, int i, int j, int row, int col) { if (j == col) { return Int32.MinValue; } if (i == 0) { return tri[i, j]; } tri[i, j] = Math.Max( maxPathSum(tri, i - 1, j, row, col), maxPathSum(tri, i - 1, j + 1, row, col)); return tri[i, j]; } /* Driver program to test above functions */ public static void Main() { int[, ] tri = new int[, ] { { 1, 5, 3 }, { 4, 8, 0 }, { 1, 0, 0 } }; Console.WriteLine(maxPathSum(tri, 2, 0, 2, 2)); }}// This code is contributed by phasing17 |
Javascript
// JavaScript program for// Recursive implementation of// Max sum problem in a triangle let N = 3// Function for finding maximum sumfunction maxPathSum(tri, i, j, row, col){ if(j == col ){ return Number.MIN_SAFE_INTEGER; } if(i == 0 ){ 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, 5, 3 ], [ 4, 8, 0 ], [ 1, 0, 0 ]];console.log(maxPathSum(tri, 2, 0, 2, 2));// This code is contributed by phasing17 |
Output
14
Complexity Analysis:
- Time Complexity: O(2N*N)
- Space Complexity: O(N)
Method 2: DP Top-Down
So, after converting our input triangle elements into a regular matrix we should apply the dynamic programming concept to find the maximum path sum.
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 sumint maxPathSum(int tri[][N], int i, int j, int row, int col, vector<vector<int>> &dp){ if(j == col ){ return INT_MIN; } if(i == 0 ){ 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, 5, 3 }, { 4, 8, 0 }, { 1, 0, 0 } }; vector<vector<int>> dp(N, vector<int>(N, -1) ) ; cout << maxPathSum(tri, 2, 0, 2, 2, dp); return 0;} |
Java
// Java program for// Recursive implementation of// Max sum problem in a triangle import java.util.*;class GFG{ static int N = 3; // Function for finding maximum sum static int maxPathSum(int tri[][], int i, int j, int row, int col, int dp[][]){ if(j == col ){ return Integer.MIN_VALUE ; } if(i == 0 ){ 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)) ; } /* Driver program to test above functions */ public static void main(String[] args) { int tri[][] = { { 1, 5, 3 }, { 4, 8, 0 }, { 1, 0, 0 } }; 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, 2, 0, 2, 2, dp)); }}// This code is contributed by phasing17 |
Python3
# Python program for# Recursive implementation of# Max sum problem in a triangleN = 3# Function for finding maximum sumdef maxPathSum(tri, i, j, row, col, dp): if (j == col) : return -1000000; if (i == 0) : return tri[i][j]; if (dp[i][j] != -1) : return dp[i][j]; 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, 5, 3 ], [ 4, 8, 0 ], [ 1, 0, 0 ] ];dp = [[-1 for _ in range(N)] for _ in range(N)]print(maxPathSum(tri, 2, 0, 2, 2, dp));# This code is contributed by phasing17 |
C#
// C# program for// Recursive implementation of// Max sum problem in a triangle using System;using System.Collections.Generic;class GFG{ static int N = 3; // Function for finding maximum sum static int maxPathSum(int[, ] tri, int i, int j, int row, int col, int[, ] dp){ if(j == col ){ return Int32.MinValue ; } if(i == 0 ){ 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)) ; } /* Driver program to test above functions */ public static void Main(string[] args) { int[, ] tri = new int[, ] { { 1, 5, 3 }, { 4, 8, 0 }, { 1, 0, 0 } }; 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, 2, 0, 2, 2, dp)); }}// This code is contributed by phasing17 |
Javascript
// JS program for// Recursive implementation of// Max sum problem in a trianglevar N = 3 // Function for finding maximum sum function maxPathSum(tri, i, j, row, col, dp){ if (j == col) { return -1000000; } if (i == 0) { return tri[i][j]; } if (dp[i][j] != -1) { return dp[i][j]; } 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, 5, 3 ], [ 4, 8, 0 ], [ 1, 0, 0 ] ];let dp = new Array(N);for (var i = 0; i < N; i++) dp[i] = [... new Array(N).fill(-1)];console.log(maxPathSum(tri, 2, 0, 2, 2, dp));// This code is contributed by phasing17 |
Output
14
Complexity Analysis:
- Time Complexity: O(m*n) where m = no of rows and n = no of columns
- Space Complexity: O(n2)
Method 3: DP Bottom-Up
Applying, DP in a bottom-up manner we should solve our problem as:
Example :
8 5 9 3 2 4 6 7 4 3 Step 1 : 8 5 9 3 2 4 6 0 7 4 0 0 3 0 0 0 Step 2 : 8 5 9 3 2 4 6 0 10 7 0 0 Step 3 : 8 5 9 3 12 14 13 0 Step 4: 20 19 23 16 Output : 23
Below is the implementation of the above approach:
C++
// C++ program implementation of// Max sum problem in a triangle#include <bits/stdc++.h>using namespace std;#define N 3// Function for finding maximum sumint maxPathSum(int tri[][N]){ int ans = 0; // Loop for bottom-up calculation for (int i = N - 2; i >= 0; i--) { for (int j = 0; j < N - i; j++) { // For each element, check both // elements just below the number // and below left to the number // add the maximum of them to it if (j - 1 >= 0) tri[i][j] += max(tri[i + 1][j], tri[i + 1][j - 1]); else tri[i][j] += tri[i + 1][j]; ans = max(ans, tri[i][j]); } } // Return the maximum sum return ans;}// Driver Codeint main(){ int tri[N][N] = { { 1, 5, 3 }, { 4, 8, 0 }, { 1, 0, 0 } }; cout << maxPathSum(tri); return 0;} |
Java
// Java program implementation of// Max sum problem in a triangleclass GFG{ static int N = 3; // Function for finding maximum sum static int maxPathSum(int tri[][]) { int ans = 0; // Loop for bottom-up calculation for (int i = N - 2; i >= 0; i--) { for (int j = 0; j < N - i; j++) { // For each element, check both // elements just below the number // and below left to the number // add the maximum of them to it if (j - 1 >= 0) tri[i][j] += Math.max(tri[i + 1][j], tri[i + 1][j - 1]); else tri[i][j] += tri[i + 1][j]; ans = Math.max(ans, tri[i][j]); } } // Return the maximum sum return ans; } // Driver Code public static void main(String []args) { int tri[][] = { { 1, 5, 3 }, { 4, 8, 0 }, { 1, 0, 0 } }; System.out.println(maxPathSum(tri)); }}// This code is contributed by ihritik |
Python3
# Python program implementation of# Max sum problem in a triangleN = 3# Function for finding maximum sumdef maxPathSum( tri ): ans = 0; # Loop for bottom-up calculation for i in range(N - 2, -1, -1): for j in range(0 , N - i): # For each element, check both # elements just below the number # and below left to the number # add the maximum of them to it if (j - 1 >= 0): tri[i][j] += max(tri[i + 1][j], tri[i + 1][j - 1]); else: tri[i][j] += tri[i + 1][j]; ans = max(ans, tri[i][j]); # Return the maximum sum return ans # Driver Code tri = [ [ 1, 5, 3 ], [ 4, 8, 0 ], [ 1, 0, 0 ] ]print(maxPathSum(tri))# This code is contributed by ihritik |
C#
// C# program implementation of// Max sum problem in a triangleusing System;class GFG{ static int N = 3; // Function for finding maximum sum static int maxPathSum(int [,]tri) { int ans = 0; // Loop for bottom-up calculation for (int i = N - 2; i >= 0; i--) { for (int j = 0; j < N - i; j++) { // For each element, check both // elements just below the number // and below left to the number // add the maximum of them to it if (j - 1 >= 0) tri[i, j] += Math.Max(tri[i + 1, j], tri[i + 1, j - 1]); else tri[i, j] += tri[i + 1, j]; ans = Math.Max(ans, tri[i, j]); } } // Return the maximum sum return ans; } // Driver Code public static void Main() { int[,] tri = { { 1, 5, 3 }, { 4, 8, 0 }, { 1, 0, 0 } }; Console.WriteLine(maxPathSum(tri)); }}// This code is contributed by ihritik |
PHP
<?php// PHP program implementation of// Max sum problem in a triangle$N = 3;// Function for finding maximum sumfunction maxPathSum($tri){ global $N; $ans = 0; // Loop for bottom-up calculation for ($i = $N - 2; $i >= 0; $i--) { for ($j = 0; $j < $N - $i; $j++) { // For each element, check both // elements just below the number // and below left to the number // add the maximum of them to it if ($j - 1 >= 0) $tri[$i][$j] += max($tri[$i + 1][$j], $tri[$i + 1][$j - 1]); else $tri[$i][$j] += $tri[$i + 1][$j]; $ans = max($ans, $tri[$i][$j]); } } // Return the maximum sum return $ans;}// Driver Code$tri = array(array( 1, 5, 3 ), array( 4, 8, 0 ), array( 1, 0, 0 ));echo maxPathSum($tri);// This code is contributed by chandan_jnu?> |
Javascript
<script>//Javascript program implementation of// Max sum problem in a triangleN = 3;// Function for finding maximum sumfunction maxPathSum(tri){ var ans = 0; // Loop for bottom-up calculation for (var i = N - 2; i >= 0; i--) { for (var j = 0; j < N - i; j++) { // For each element, check both // elements just below the number // and below left to the number // add the maximum of them to it if (j - 1 >= 0) tri[i][j] += Math.max(tri[i + 1][j], tri[i + 1][j - 1]); else tri[i][j] += tri[i + 1][j]; ans = Math.max(ans, tri[i][j]); } } // Return the maximum sum return ans;} var tri = [[ 1, 5, 3 ], [ 4, 8, 0 ], [ 1, 0, 0 ]]; document.write(maxPathSum(tri));//This code is contributed by SoumikMondal</script> |
Output
14
Time Complexity: O(N2)
Auxiliary Space: O(1)
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!
