I have spent many hours trying to solve the SUMTRIAN problem (SUMTRIAN Problem - CodeChef) I know how my program works, I am implementing recursion, and I am doing my best to implement memoization (this is new for me). The code works perfectly fine for small triangles. However, every submission to CodeChef exceeds the time limit. Can anyone give me any pointers, please?
Thanks,
public class Main {
private static int[][] triangle = new int[0][0];
private static int[][] computedPaths = new int[0][0]; //for memoization
public static void main(String[] args){
java.util.Scanner input = new java.util.Scanner(System.in);
int cases = input.nextInt();
int[] solutions = new int[cases];
int solutionsIndex = 0;
for(int i = 0; i < cases; i += 1){//for each triangle
int lines = input.nextInt();
triangle = new int[lines][lines];
computedPaths = new int[lines][lines];
int level = 1; //top of triangle is level 1 and level increases as works towards base
for(int y = 0; y < lines; y += 1){
for(int x = 0; x < level; x += 1){
triangle[y][x] = input.nextInt();
}
level += 1;
}
//save outputs in array until all inputs are processed
solutions[solutionsIndex] = findGreatestRouteValueRecursively(0,0);
solutionsIndex += 1;
}
for(int i = 0; i < solutions.length; i += 1){
System.out.println(solutions[i]);
}
}//end main
public static int findGreatestRouteValueRecursively(int y, int x){
if(y >= triangle.length)
return 0;
else if(computedPaths[y][x] == 0){
int value1 = findGreatestRouteValueRecursively(y+1, x);
int value2 = findGreatestRouteValueRecursively(y+1, x+1);
computedPaths[y][x] = Math.max(value1, value2) + triangle[y][x];
}
return computedPaths[y][x];
}//end findGreatestRouteValueRecursively()
}
bump - any tips on how to memoize this would be greatly appreciated! the only code to rly look at is the findGreatestRouteValueRecursively at the bottom
Solved - for anyone curious, what made the difference was changing my input from Scanner to BufferedReader and InputStreamReader. Lesson learned 
Code below:
public class SumsInATriangle {
private static int[][] triangle = new int[0][0];
private static int[][] computedPaths = new int[0][0]; //for memoization
public static void main(String[] args) throws java.io.IOException{
java.io.BufferedReader reader = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
String[] in = reader.readLine().split(" ");
int cases = Integer.parseInt(in[0]);
int[] solutions = new int[cases];
int solutionsIndex = 0;
for(int i = 0; i < cases; i += 1){//for each triangle
in = reader.readLine().split(" ");
int lines = Integer.parseInt(in[0]);
triangle = new int[lines][lines];
computedPaths = new int[lines][lines];
int level = 1; //top of triangle is level 1 and level increases as works towards base
for(int y = 0; y < lines; y += 1){
in = reader.readLine().split(" ");
for(int x = 0; x < level; x += 1){
triangle[y][x] = Integer.parseInt(in[x]);
}
level += 1;
}
//save outputs in array until all inputs are processed
solutions[solutionsIndex] = findGreatestRouteValueRecursively(0,0);
solutionsIndex += 1;
}
for(int i = 0; i < solutions.length; i += 1){
System.out.println(solutions[i]);
}
// int level = 1; //print triangle
// for(int y = 0; y < triangle[0].length; y += 1, level += 1){
// for(int x = 0; x < level; x += 1){
// System.out.print(triangle[y][x] + " ");
// }
// System.out.println();
// }
}//end main
public static int findGreatestRouteValueRecursively(int y, int x){
if(y >= triangle.length)
return 0;
else if(computedPaths[y][x] == 0){
int value1 = findGreatestRouteValueRecursively(y+1, x);
int value2 = findGreatestRouteValueRecursively(y+1, x+1);
computedPaths[y][x] = Math.max(value1, value2) + triangle[y][x];
}
return computedPaths[y][x];
}//end findGreatestRouteValueRecursively()
}//end class