View Code of Problem 65

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int t= Integer.parseInt(scanner.nextLine());
        while (t-->0){
            int n= Integer.parseInt(scanner.nextLine());
            int[][] matrix=new int[n][n];
            for(int i=0;i<n;i++){
                String[] strings=scanner.nextLine().split(" ");
                int l=0;
                for(int j=0;j<strings.length;j++){
                    if(!strings[j].equals("")){
                        matrix[i][l++]= Integer.parseInt(strings[j]);
                    }
                }
            }
            int[][] dp=new int[n][n];
            dp[0][0]=matrix[0][0];
            for(int i=1;i<n;i++){
                for(int j=0;j<=i;j++){
                    if(j==0){
                        dp[i][j]=dp[i-1][j]+matrix[i][j];
                    }
                    else if(j==i){
                        dp[i][j]=dp[i-1][j-1]+matrix[i][j];
                    }
                    else{
                        dp[i][j]=matrix[i][j]+Math.max(dp[i-1][j-1],dp[i-1][j]);
                    }
                }
            }
            Arrays.sort(dp[n-1]);
            System.out.println(dp[n-1][n-1]);
        }

    }
}