## 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[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 –

- Storage Allocation in Block Structured Language
- Reading Initialization Parameters in Servlets
- SLR Parsing Table Construction Example
- Path with Maximum Sum in a Triangular Pattern
- Access To Nonlocal Names in Compiler Design

Other Resources:-