7362: CodeChef SUMTRIAN - Sums in a Triangle
[Creator : ]
Description
Given an integer N, let us consider a triangle of numbers of N lines in which a number $a_{11}$ appears in the first line, two numbers $a_{21}$ and $a_{22}$ appear in the second line, three numbers $a_{31}, a_{32}$ and $a_{33}$ appear in the third line, etc. In general, i numbers $a_{i1}, a_{i2} \dots a_{ii}$ appear in the $i^{th}$ line for all $1 \leq i \leq N$.
Develop a program that will compute the largest of the sums of numbers that appear on the paths starting from the top towards the base, so that:
Develop a program that 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.
Input
The first line of the input contains an integer $T$, the number of test cases.
Then T test cases follow. Each test case starts with an integer $N$, the number of rows.
Then $N$ lines follow where in $i^{th}$ line contains i integers $a_{i1}, a_{i2} \dots a_{ii}$.
Then T test cases follow. Each test case starts with an integer $N$, the number of rows.
Then $N$ lines follow where in $i^{th}$ line contains i integers $a_{i1}, a_{i2} \dots a_{ii}$.
Output
For each test case print the maximum path sum in a separate line.
Constraints
$1≤T≤1000$
$1 \leq N \lt 100$
$0 \leq a_{ij} \lt 100$
$1 \leq N \lt 100$
$0 \leq a_{ij} \lt 100$
Sample 1 Input
2
3
1
2 1
1 2 3
4
1
1 2
4 1 2
2 3 1 1
Sample 1 Output
5
9
Test case 1:
There are a total of 4 paths
Test case 2:
There are a total of 8 paths
There are a total of 4 paths
- (1,1)→(2,1)→(3,1) with sum equal to 4.
- (1,1)→(2,1)→(3,2) with sum equal to 5.
- (1,1)→(2,2)→(3,2) with sum equal to 4.
- (1,1)→(2,2)→(3,3) with sum equal to 5.
Test case 2:
There are a total of 8 paths
- (1,1)→(2,1)→(3,1)→(4,1) with sum equal to 8.
- (1,1)→(2,1)→(3,1)→(4,2) with sum equal to 9.
- (1,1)→(2,1)→(3,2)→(4,2) with sum equal to 7.
- (1,1)→(2,1)→(3,2)→(4,3) with sum equal to 4.
- (1,1)→(2,2)→(3,2)→(4,2) with sum equal to 7.
- (1,1)→(2,2)→(3,2)→(4,3) with sum equal to 5.
- (1,1)→(2,2)→(3,3)→(4,3) with sum equal to 6.
- (1,1)→(2,2)→(3,3)→(4,4) with sum equal to 6.