Path with Maximum Sum in a Triangular Pattern

0
610

Path with Maximum Sum in a Triangular Pattern

In this article you will learn in details Path with Maximum Sum in a Triangular Pattern so read article.

Path with Maximum Sum in a Triangular Pattern
Path with Maximum Sum in a Triangular Pattern

We have numbers in the form of a triangle; find the maximum sum from top to bottom by beginning at the top of the triangle and moving to adjacent numbers on the row below.
Consider the following 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 

We can use brute force by testing any possible course, but this will take a long time. Instead, we can try to solve this problem using dynamic programming, which will reduce the time complexity.

Our problem appears to be a minimal cost path if we left shift every element and place 0 in each empty position to make it a normal matrix.
We can use the dynamic programmic principle to find the maximum path sum after transforming our input triangle elements into a normal matrix.
Using DP in a bottom-up approach, we can solve our problem as follows:

Consider the following scenario:

 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++ 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;
}
Output : 
 

14

Read More –

Other Resources:-

Pascal’s Triangle

LEAVE A REPLY

Please enter your comment!
Please enter your name here