 # Find the maximum sum of the numbers From Triangle. RSS

## 1 reply

Last post Jan 15, 2019 09:34 AM by Yuki Tao

• ### Find the maximum sum of the numbers From Triangle.

Jan 15, 2019 05:52 AM|FarhatKhan|LINK

Here are the rules for finding max number from triangle.

. You will start from the top and move downwards to an adjacent number as in below.

1. You are only allowed to walk downwards and diagonally.
2. You should walk over the numbers as evens and odds subsequently. Suppose that you are on an even number the next number you walk must be odd, or if you are stepping over an odd number the next number must be even. In other words, the final path would be like odd -> even -> odd -> even …
3. You must reach to the bottom of the pyramid.

Your goal is to find the maximum sum if you walk the path. Assume that there is at least 1 valid path to the bottom. If there are multiple paths giving the same sum, you can choose any of them.

Sample Input:

1

8 9

1 5 9

4 5 2 3

Output:

Max sum: 16 Path: 1, 8, 5, 2

Explanation:

As you can see this triangle has several paths: 1->8->5->2, 1->9->9->3, 1->8->1->4, etc… The correct answer is 1 + 8 + 5 + 2 = 16.  Because since 1 (top most number) is odd we cannot walk onto 9 because 9 is an odd number too. The only place we can step is 8. From 8 we can walk to 1 or 5. But only 1 -> 8 -> 5 -> 2 sequence gives us the maximum sum. The other path 1-> 8 -> 1 -> 4 is also a valid path but it sums up to 14. Since 16 is greater than 14, 16 is the solution. Also, note that the solution is in the form of odd > even > odd > even.

• ### Re: Find the maximum sum of the numbers From Triangle.

Jan 15, 2019 09:34 AM|Yuki Tao|LINK

Hi FarhatKhan，

According to your requirement,

I suggest you could refer to these links,they are similar to your need,

You only need to add the judgment of odd/even numbers in finding the maximum path.

https://www.mathblog.dk/project-euler-18/

https://www.geeksforgeeks.org/maximum-path-sum-triangle/

Best Regards.

Yuki Tao

MSDN Community Support
Please remember to click "Mark as Answer" the responses that resolved your issue.
If you have any compliments or complaints to MSDN Support, feel free to contact MSDNFSF@microsoft.com.