sum in a triangle

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
abhi
Learning poster
Posts: 94
Joined: Fri Nov 25, 2005 7:29 pm

sum in a triangle

Post by abhi »

can anybody help me to solve this problem . i dint seem to understand it ....


Let us consider a triangle of numbers in which a number appears in the first line, two numbers appear in the second line etc. Develop a program which will compute the largest of the sums of numbers that appear on the paths starting from the top towards the base, so that:

on each path the next number is located on the row below, more precisely either directly below or below and one place to the right;
the number of rows is strictly positive, but less than 100;
all numbers are positive integers between O and 99.


Input
In the first line integer n - the number of test cases (equal to about 1000). Then n test cases follow. Each test case starts with the number of lines which is followed by their content.

Output
For each test case write the determined value in a separate line.

Example
Input:
2
3
1
2 1
1 2 3
4
1
1 2
4 1 2
2 3 1 1

Output:
5
9

The^Guard
New poster
Posts: 6
Joined: Wed Nov 23, 2005 11:16 pm

Post by The^Guard »

Solve the problem from the bottom (wide end) of the triangle, not from the top. Look at the pairs of integers and choose the larger of the pair as the choice that must be made by the integer centered above the pair. Once that insight comes through, the rest of the solution is simple and very speedy.


for (i=n-1; i>=1; i--)
for (j=0; j<=i; j++)
A[j] = A[j] + MAX(A[i+1][j], A[i+1][j+1]);

Post Reply

Return to “Algorithms”