Miscellany

import java.io.*;
import java.util.*;

class Trekendeshi
{
	public static void main(String[] args) throws IOException
	{
		int rreshtat, a, b = 0;
		int[] vargu;
		int[][] trekendeshi;
		BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
		System.out.println("Fut numrin e rreshtave te pemes:");
		rreshtat = Integer.parseInt(stdin.readLine());
		a = rreshtat;
		trekendeshi = new int[rreshtat][rreshtat];
		while(rreshtat > 0)
		{
			System.out.println("Fut rreshtin " + (a - rreshtat + 1) + ":");
			String[] ndarja = (stdin.readLine()).split(" ");
			for(int i = 0; i < ndarja.length; i++) trekendeshi[b][i] = Integer.parseInt(ndarja[i]);
			b++;
			rreshtat--;
		}
		vargu = new int[rreshtat];
		vargu = largestSum(trekendeshi, 0, 0, vargu);
		for(int i =0; i < vargu.length; i++) System.out.print(vargu[i] + " ");
		System.out.println("\n" + sum(vargu));
		System.out.println(lg(trekendeshi, 0, 0));
	}

	public static int lg(int[][] trekendeshi, int i, int j)
	{
		int sum1 = 0, sum2 = 0;
		if(i < trekendeshi.length && j < trekendeshi.length)
		{
			sum1 = trekendeshi[i][j] + lg(trekendeshi, i+1, j);
			sum2 = trekendeshi[i][j] + lg(trekendeshi, i+1, j+1);
		}
		if(sum1 > sum2) return sum1;
		else return sum2;
	}

	public static int[] largestSum(int[][] trekendeshi, int i, int j, int[] vargu)
	{
		int[] vargu1 = vargu, vargu2 = vargu;
		if(i < trekendeshi.length && j < trekendeshi.length)
		{
			vargu1[i] = trekendeshi[i][j];
			vargu1 = largestSum(trekendeshi, i+1, j, vargu1);
			vargu2[i] = trekendeshi[i][j];
			vargu2 = largestSum(trekendeshi, i+1, j+1, vargu2);
		}
		if(sum(vargu1) > sum(vargu2)) return vargu1;
		else return vargu2;
	}

	public static int sum(int[] array)
	{
		int sum = 0;
		for(int i = 0; i < array.length; i++) sum += array[i];
		return sum;
	}
}