# Sums in a Triangle | CodeChef Solution

Hello coders, today we are going to solve Sums in a Triangle CodeChef Solution whose Problem Code is SUMTRIAN.

Contents

Let’s consider a triangle of numbers in which a number appears in the first line, two numbers appear in the second line, three in the third 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 0 and 99.

## Input Format

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 Format

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

Example

Sample Input

``````2
3
1
2 1
1 2 3
4
1
1 2
4 1 2
2 3 1 1 ``````

Sample Output

``````5
9``````

## Solution – Sums in a Triangle | CodeChef Solution

### C++

```#include<bits/stdc++.h>
using namespace std;
int main(){
int i,j,t,n;
cin>>t;
while(t--){
cin>>n;
int a[n][n];
for(int i=0;i<n;i++){
for(j=0;j<=i;j++){
cin>>a[i][j];
}
}
for(int i=n-2;i>=0;i--){
for(j=0;j<=i;j++){
if((a[i][j]+a[i+1][j])>(a[i][j]+a[i+1][j+1]))
a[i][j]=a[i][j]+a[i+1][j];
else
a[i][j]=a[i][j]+a[i+1][j+1];

}
}
cout<<a<<endl;
}
return 0;
}
```

### Python

```#Solution Provided by CodingBroz
T = int(input())
for i in range(T):
l = []
m = int(input())
for j in range(m):
n = list(map(int, input().split()))
l.append(n)

for j in range(m - 2, -1, -1):
for k in range(0, j+1):
l[j][k] += max(l[j+1][k], l[j+1][k+1])
print(l)

```

### Java

```/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Scanner sc = new Scanner(System.in);
int testcases = sc.nextInt();
for(int i=0;i<testcases;i++)
{
int rows = sc.nextInt();
int sum=0;
int triangle[][] = new int[rows][rows];
for(int j=0;j<rows;j++)
for(int k=0;k<=j;k++)
triangle[j][k]=sc.nextInt();
for(int j=rows-2;j>=0;j--)
{
for(int k=0;k<=j;k++)
{
triangle[j][k]+= Math.max(triangle[j+1][k],triangle[j+1][k+1]);
}
}
System.out.println(triangle);
}
}
}
```

Disclaimer: The above Problem (Sums in a Triangle) is generated by CodeChef but the Solution is Provided by CodingBroz. This tutorial is only for Educational and Learning Purpose.