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.

Task

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[0][0]<<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[0][0])
    

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[0][0]);
		}
	}
}

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.