Hello coders, today we are going to solve Sums in a Triangle CodeChef Solution whose Problem Code is SUMTRIAN.
Problem
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
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
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
Sums in a Triangle CodeChef Solution in Python
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[0][0])Sums in a Triangle CodeChef Solution in CPP
#include <iostream>
#include <cmath>
using namespace std;
int main() {
// your code goes here
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int a[n][n];
for(int i=0;i<n;i++)
{
for(int j=0;j<=i;j++)
{
cin>>a[i][j];
}
}
for(int i=n-2;i>=0;i--)
{
for(int j=0;j<n-1;j++)
{
a[i][j]=a[i][j]+max(a[i+1][j],a[i+1][j+1]);
}
}
cout<<a[0][0]<<endl;
}
return 0;
}Sums in a Triangle CodeChef Solution in JAVA
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[0][0]);
}
}
}Disclaimer: The above Problem (Sums in a Triangle) is generated by CodeChef but the solution is provided by Chase2learn.This tutorial is only for Educational and Learning purpose.
