Project Euler #67: Maximum path sum II

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23. The path is denoted by numbers in bold.

3
4
6
3

That is, 3+7+4+9=23.

Find the maximum total from top to bottom of the triangle given in input.

Input Format
First line contains T, the number of testcases. For each testcase:
First line contains N, the number of rows in the triangle.
For next N lines, i‘th line contains i numbers.

Output Format
Print the required answer for each testcase on a new line.

Constraints
1T10
1N100
Each element of triangle lies between 0 and 100(both inclusive).

Sample Input

2
4
3
7 4
2 4 6
8 5 9 3
4
3
7 4
2 4 6
8 5 9 3

Sample Output

23
23

Java:

import java.util.Arrays;
import java.util.Scanner;
import java.util.TreeMap;
import java.math.BigInteger;

public class Solution {
private static int[][] matrix;
private static Scanner input = new Scanner(System.in);

public static void main(String[] args)
{
int N = 0, T = 0;
T = input.nextInt();
for(int count1 = 1; count1 <= T; ++count1)
{
N = input.nextInt();
//input matrix
if(N == 1){
System.out.println(input.nextInt());
}
else if(N == 2){
int root = input.nextInt();
int left = input.nextInt();
int right = input.nextInt();
int max1 = root + left;
int max2 = root + right;
if(max1 < max2)
System.out.println(max2);
else
System.out.println(max1);
}
else if(N >= 3){
matrix = new int[N][N];

int row = N – 2;
int start = 1;
for(int count2 = 0; count2 < N; ++count2)
{
for(int count3 = 0; count3 < start; ++count3)
matrix[count2][count3] = input.nextInt();
++start;
}

do
{
for(int count2 = 0; count2 < row+1; ++count2)
{
matrix[row][count2] += (int)Math.max(matrix[row+1][count2], matrix[row+1][count2+1]);
}
–row;
}while(row >= 1);
int max1 = matrix[0][0] + matrix[1][0];
int max2 = matrix[0][0] + matrix[1][1];
if(max1 < max2)
System.out.println(max2);
else
System.out.println(max1);
}
}

}
}

Advertisements