Sums in a Triangle - CodeChef Solution

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

👊 Table of Contents

• Task
• Input
• Output
• Example
• Solution - Sums in a Triangle

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

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

Solution - Sums in a Triangle - CodeChef Solution 

Python 3 

#Solution Provided by Sloth Coders 
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])

C++

#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;
}

C

#include <stdio.h>

int max(int a,int b){
    if(a > b){
        return a;
    }
    return b;
}

int main(void) {
	int t, n;
	scanf("%d",&t);
	for(int test=1;test<=t;test++){
	    scanf("%d",&n);
	    int a[n][n];
	    for(int i=0;i<n;i++){
	        for(int j=0;j<=i;j++){
	            scanf("%d",&(a[i][j]));
	        }
	    }
	    for(int i=n-2;i>=0;i--){
	        for(int j=0;j<=i;j++){
	            a[i][j] += max(a[i+1][j],a[i+1][j+1]);
	        }
	    }
	    printf("%d\n",a[0][0]);
	}
	return 0;
}

Java

import java.util.*;

class Codechef
{ 
	public static void main (String[] args)
	{
	    try{
    	    Scanner sc=new Scanner(System.in);
    		int t=sc.nextInt();
    		while(t-->0){
    		    int n=sc.nextInt();
    		    int arr[][]=new int [n][n];
    		    for(int i=0;i<n;i++){
    		        for(int j=0;j<=i;j++){
    		            arr[i][j]=sc.nextInt();
    		        } } 
    		    for(int i=n-2;i>=0;i--){
    		        for(int j=0;j<=i;j++){
    		            if((arr[i][j]+arr[i+1][j])>(arr[i][j]+arr[i+1][j+1])){
    		                arr[i][j]=arr[i][j] + arr[i+1][j]; }
    		            else{
    		                arr[i][j]=arr[i][j] + arr[i+1][j+1]; }
    		        }  }
    		    System.out.println(arr[0][0]);
    		}  }
	   catch(Exception e){ }
} }

Disclaimer: The above Problem (Sums in a Triangle) is generated by CodeChef but the Solution is provided by Sloth Coders.

Also Read:

• Primality Test - CodeChef Solution 
• Total Expense - CodeChef Solution 
• World Record - CodeChef Solution 
• Valid Pair - CodeChef Solution 
• Fit Squares in Triangles - CodeChef Solution