What is the error in this code?

I have been trying to solve the SUMTRIAN problem. I wrote a code and it’s working fine with the given input as well as some of my own inputs which i manually tested. Still the compiler for the problem submission is showing wrong answer. Please can someone tell me what am I doing wrong?

Here is the code

import java.util.Scanner;

public class SUMTRIAN {
public static void main(String[] args){
	Scanner in = new Scanner(System.in);
	int n;int lines;
	n = in.nextInt();
	for(int i=0;i<n;i++){
	lines = in.nextInt();
		int array[][] = new int[lines][lines];
			for(int j=0;j<lines;j++){
			
				for(int c=0;c<=j;c++){
					array[j][c]=in.nextInt();
				}
			}			
			int start = array[0][0] ;int counter = 0;
			for(int count= 1;count<lines;count++){
				
				if(count==lines-1){
					if(array[count][counter]>=array[count][counter+1]){
						start+=array[count][counter];
					}
					else if(array[count][counter]<=array[count][counter+1]){
						start+=array[count][counter+1];
					}
					break;
				}
				if(array[count][counter]>=array[count][counter+1]){
					start+=array[count][counter];
				}
				else if(array[count][counter]<array[count][counter+1]){
					if((array[count+1][counter+1]+array[count][counter+1])>(array[count][counter]+array[count+1][counter])){
						start+=array[count][counter+1];
						counter+=1;	
					}
					else if((array[count+1][counter+1]+array[count][counter+1])<(array[count][counter]+array[count+1][counter])){
						start+=array[count][counter];
					}
					
				}
			}
			System.out.println(start);
	}	
}
}

Consider the input triangle

1
1 2
1 1 1
9 1 1 1

Your code will choose the path

[1]
 1 [2]
 1 [1] 1
 9 [1] 1  1

…whereas the best path is

[1]
[1] 2
[1] 1  1
[9] 1  1  1

This is because you are following a greedy strategy, which is not guaranteed to lead to the best solution here. The correct way to solve this problem is with the help of dynamic programming. You can refer to this answer by @kuruma for a better understanding of this problem, and you will find various resources on the internet on dynamic programming in general. Feel free to ask if something is not clear :slight_smile:

2 Likes

alright! I’ll look into dynamic programming, thanks for making me understand which cases will not work. Cheers!

//