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.

Codechef solutions

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.

Leave a Comment