Codechef -> Practice -> Easy -> SumsInATriangle

Problem Link : http://www.codechef.com/problems/SUMTRIAN

Solution :

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.io.PrintWriter;

/**

 *

 * @author XCoder

 */

class SumsInATriangle_DynamicProgramming {

    public static int readIntLine() throws IOException {

        return Integer.parseInt(br.readLine());

    }

    public static long readLongLine() throws IOException {

        return Long.parseLong(br.readLine());

    }

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    private static PrintWriter pw = new PrintWriter(System.out);

    public static void main(String[] args) throws IOException {

        int test = readIntLine();

        while (test-- > 0) {

            int matrixsize = readIntLine();

            int a[][] = new int[matrixsize][matrixsize];

            int count = matrixsize;

            while (count-- > 0) {

                String str = br.readLine();

                String split[] = str.split(" ");

                int b[] = new int[split.length];

                for (int i = 0; i < b.length; i++) {

                    b[i] = Integer.parseInt(split[i]);

                }

//                System.out.println("mmm");

//                System.out.println(matrixsize);

//                System.out.println(count);

//                System.out.println(split.length);

                if (matrixsize == count + 1) {

                    a[0][0] = b[0];

                    continue;

                }

                int i = matrixsize - count - 1;

                for (int j = 0; j <= i; j++) {

                    if (j == 0) {

                        a[i][j] = a[i - 1][j] + b[j];

                    } else if (i == j) {

                        a[i][j] = a[i - 1][j - 1] + b[j];

                    } else {

                        int max = a[i - 1][j] > a[i - 1][j - 1] ? a[i - 1][j] : a[i - 1][j - 1];

                        a[i][j] = max + b[j];

                    }

                }

//                for (int j = 0; j < b.length; j++) {

//                    System.out.print(a[i][j] + "  ");

//                }

//                System.out.println("");

            }

            int max = 0;

            for (int i = 0; i < matrixsize; i++) {

                if (max < a[matrixsize - 1][i]) {

                    max = a[matrixsize - 1][i];

                }

            }

//            System.out.println("Answer is " + max);

            pw.println(max);

            pw.flush();

        }

    }

}