Sums in a Triangle Codechef Solution

Hello Programmers In this post, you will know how to solve the Sums in a Triangle CodeChef Solution. The Problem Code is SUMTRIAN.

One more thing to add, don’t directly look for the solutions, first try to solve the problems of Codechef by yourself. If you find any difficulty after trying several times, then you can look for 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 Solutions 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 Solutions 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 Solutions 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 BrokenProgrammers. This tutorial is only for Educational and Learning purpose.

Note:- I compile all programs, if there is any case program is not working and showing an error please let me know in the comment section. If you are using adblocker, please disable adblocker because some functions of the site may not work correctly.

Next: Queen Blocks Codechef Solution