Still practicing for Facebook Hacker Cup 2013. The problem below is a classic, although I wouldn’t necessarily classify it as “easy” as the guys from CodeChef did. Anyway here you go:

———-
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 O 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

Input:
2
3
1
2 1
1 2 3
4
1
1 2
4 1 2
2 3 1 1

Output:
5
9
———-

My Solution

Solving this problem with a brute force approach is possible, especially if the input is small, as in this case. However, as the input size grows the brute force approach stops working, as the number of possible paths you’ll need to calculate grows exponentially.

There’s a rather clever way to solve this in linear time: start with the second to last row. Then for each of the numbers there calculate what is the maximum value they can achieve going down, which is basically the numbers themselves plus the max out of the two numbers below. Then repeat this process going up the pyramid, and once you get on top that will be your answer.

#include <stdio.h>

int mat[100][100];

int max(int x, int y){
  if(x>y)
    return x;
  else
    return y;
}

int solve(int x){
  int k,l;

  if(x==1)
    return mat[0][0];
  
  for(k=x-2;k>=0;k--){
    for(l=0;l<=k;l++){
      mat[k][l] += max(mat[k+1][l],mat[k+1][l+1]);
    }
  }

  return mat[0][0];
}

int main(){
  int i,j,k,l,w;
  scanf("%d",&j);
  int x;

  for (i=0;i<j;i++){
    scanf("%d",&x);    
    for(k=0;k<x;k++){
      for(l=0;l<k+1;l++){
        scanf("%d",&w);  
        mat[k][l]=w;
      }
    }
    printf("%dn",solve(x));
  }  

return 0;
}