# 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.

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;
}

/* 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``````