MaximumPathSum.java

package devjava;

public class MaximumPathSum {

	static void printTree(int[][] tree) {
		for (int i = 0; i < tree.length; i++) {
			for (int j = 0; j < tree[i].length; j++) {
				System.out.print(tree[i][j] + "(" + i + "" + j + ") ");
			}
			System.out.println();
		}
	}

	public static void main(String[] args) {
		int[][] smallTree = { { 3, 0, 0, 0 }, { 7, 4, 0, 0 }, { 2, 4, 6, 0 }, { 8, 5, 9, 3 } };
		int[][] mediumTree = { { 75, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
				{ 95, 64, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 17, 47, 82, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
				{ 18, 35, 87, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
				{ 20, 04, 82, 47, 65, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
				{ 19, 01, 23, 75, 03, 34, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
				{ 88, 02, 77, 73, 07, 63, 67, 0, 0, 0, 0, 0, 0, 0, 0 },
				{ 99, 65, 04, 28, 06, 16, 70, 92, 0, 0, 0, 0, 0, 0, 0 },
				{ 41, 41, 26, 56, 83, 40, 80, 70, 33, 0, 0, 0, 0, 0, 0 },
				{ 41, 48, 72, 33, 47, 32, 37, 16, 94, 29, 0, 0, 0, 0, 0 },
				{ 53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14, 0, 0, 0, 0 },
				{ 70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57, 0, 0, 0 },
				{ 91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48, 0, 0 },
				{ 63, 66, 04, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31, 0 },
				{ 04, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 04, 23 } };
		int[][] tree = { { 59 }, { 73, 41 }, { 52, 40, 9 }, { 26, 53, 6, 34 }, { 10, 51, 87, 86, 81 },
				{ 61, 95, 66, 57, 25, 68 }, { 90, 81, 80, 38, 92, 67, 73 }, { 30, 28, 51, 76, 81, 18, 75, 44 },
				{ 84, 14, 95, 87, 62, 81, 17, 78, 58 }, { 21, 46, 71, 58, 2, 79, 62, 39, 31, 9 },
				{ 56, 34, 35, 53, 78, 31, 81, 18, 90, 93, 15 }, { 78, 53, 4, 21, 84, 93, 32, 13, 97, 11, 37, 51 },
				{ 45, 3, 81, 79, 5, 18, 78, 86, 13, 30, 63, 99, 95 },
				{ 39, 87, 96, 28, 3, 38, 42, 17, 82, 87, 58, 7, 22, 57 },
				{ 06, 17, 51, 17, 7, 93, 9, 7, 75, 97, 95, 78, 87, 8, 53 },
				{ 67, 66, 59, 60, 88, 99, 94, 65, 55, 77, 55, 34, 27, 53, 78, 28 },
				{ 76, 40, 41, 4, 87, 16, 9, 42, 75, 69, 23, 97, 30, 60, 10, 79, 87 },
				{ 12, 10, 44, 26, 21, 36, 32, 84, 98, 60, 13, 12, 36, 16, 63, 31, 91, 35 },
				{ 70, 39, 6, 5, 55, 27, 38, 48, 28, 22, 34, 35, 62, 62, 15, 14, 94, 89, 86 },
				{ 66, 56, 68, 84, 96, 21, 34, 34, 34, 81, 62, 40, 65, 54, 62, 5, 98, 3, 2, 60 },
				{ 38, 89, 46, 37, 99, 54, 34, 53, 36, 14, 70, 26, 2, 90, 45, 13, 31, 61, 83, 73, 47 },
				{ 36, 10, 63, 96, 60, 49, 41, 5, 37, 42, 14, 58, 84, 93, 96, 17, 9, 43, 5, 43, 6, 59 },
				{ 66, 57, 87, 57, 61, 28, 37, 51, 84, 73, 79, 15, 39, 95, 88, 87, 43, 39, 11, 86, 77, 74, 18 },
				{ 54, 42, 5, 79, 30, 49, 99, 73, 46, 37, 50, 2, 45, 9, 54, 52, 27, 95, 27, 65, 19, 45, 26, 45 },
				{ 71, 39, 17, 78, 76, 29, 52, 90, 18, 99, 78, 19, 35, 62, 71, 19, 23, 65, 93, 85, 49, 33, 75, 9, 2 },
				{ 33, 24, 47, 61, 60, 55, 32, 88, 57, 55, 91, 54, 46, 57, 7, 77, 98, 52, 80, 99, 24, 25, 46, 78, 79,
						5 },
				{ 92, 9, 13, 55, 10, 67, 26, 78, 76, 82, 63, 49, 51, 31, 24, 68, 5, 57, 7, 54, 69, 21, 67, 43, 17, 63,
						12 },
				{ 24, 59, 6, 8, 98, 74, 66, 26, 61, 60, 13, 3, 9, 9, 24, 30, 71, 8, 88, 70, 72, 70, 29, 90, 11, 82, 41,
						34 },
				{ 66, 82, 67, 4, 36, 60, 92, 77, 91, 85, 62, 49, 59, 61, 30, 90, 29, 94, 26, 41, 89, 4, 53, 22, 83, 41,
						9, 74, 90 },
				{ 48, 28, 26, 37, 28, 52, 77, 26, 51, 32, 18, 98, 79, 36, 62, 13, 17, 8, 19, 54, 89, 29, 73, 68, 42, 14,
						8, 16, 70, 37 },
				{ 37, 60, 69, 70, 72, 71, 9, 59, 13, 60, 38, 13, 57, 36, 9, 30, 43, 89, 30, 39, 15, 2, 44, 73, 5, 73,
						26, 63, 56, 86, 12 },
				{ 55, 55, 85, 50, 62, 99, 84, 77, 28, 85, 3, 21, 27, 22, 19, 26, 82, 69, 54, 4, 13, 7, 85, 14, 1, 15,
						70, 59, 89, 95, 10, 19 },
				{ 04, 9, 31, 92, 91, 38, 92, 86, 98, 75, 21, 5, 64, 42, 62, 84, 36, 20, 73, 42, 21, 23, 22, 51, 51, 79,
						25, 45, 85, 53, 3, 43, 22 },
				{ 75, 63, 2, 49, 14, 12, 89, 14, 60, 78, 92, 16, 44, 82, 38, 30, 72, 11, 46, 52, 90, 27, 8, 65, 78, 3,
						85, 41, 57, 79, 39, 52, 33, 48 },
				{ 78, 27, 56, 56, 39, 13, 19, 43, 86, 72, 58, 95, 39, 7, 4, 34, 21, 98, 39, 15, 39, 84, 89, 69, 84, 46,
						37, 57, 59, 35, 59, 50, 26, 15, 93 },
				{ 42, 89, 36, 27, 78, 91, 24, 11, 17, 41, 5, 94, 7, 69, 51, 96, 3, 96, 47, 90, 90, 45, 91, 20, 50, 56,
						10, 32, 36, 49, 4, 53, 85, 92, 25, 65 },
				{ 52, 9, 61, 30, 61, 97, 66, 21, 96, 92, 98, 90, 6, 34, 96, 60, 32, 69, 68, 33, 75, 84, 18, 31, 71, 50,
						84, 63, 3, 3, 19, 11, 28, 42, 75, 45, 45 },
				{ 61, 31, 61, 68, 96, 34, 49, 39, 5, 71, 76, 59, 62, 67, 6, 47, 96, 99, 34, 21, 32, 47, 52, 7, 71, 60,
						42, 72, 94, 56, 82, 83, 84, 40, 94, 87, 82, 46 },
				{ 01, 20, 60, 14, 17, 38, 26, 78, 66, 81, 45, 95, 18, 51, 98, 81, 48, 16, 53, 88, 37, 52, 69, 95, 72,
						93, 22, 34, 98, 20, 54, 27, 73, 61, 56, 63, 60, 34, 63 },
				{ 93, 42, 94, 83, 47, 61, 27, 51, 79, 79, 45, 1, 44, 73, 31, 70, 83, 42, 88, 25, 53, 51, 30, 15, 65, 94,
						80, 44, 61, 84, 12, 77, 2, 62, 2, 65, 94, 42, 14, 94 },
				{ 32, 73, 9, 67, 68, 29, 74, 98, 10, 19, 85, 48, 38, 31, 85, 67, 53, 93, 93, 77, 47, 67, 39, 72, 94, 53,
						18, 43, 77, 40, 78, 32, 29, 59, 24, 6, 2, 83, 50, 60, 66 },
				{ 32, 1, 44, 30, 16, 51, 15, 81, 98, 15, 10, 62, 86, 79, 50, 62, 45, 60, 70, 38, 31, 85, 65, 61, 64, 6,
						69, 84, 14, 22, 56, 43, 9, 48, 66, 69, 83, 91, 60, 40, 36, 61 },
				{ 92, 48, 22, 99, 15, 95, 64, 43, 1, 16, 94, 2, 99, 19, 17, 69, 11, 58, 97, 56, 89, 31, 77, 45, 67, 96,
						12, 73, 8, 20, 36, 47, 81, 44, 50, 64, 68, 85, 40, 81, 85, 52, 9 },
				{ 91, 35, 92, 45, 32, 84, 62, 15, 19, 64, 21, 66, 6, 1, 52, 80, 62, 59, 12, 25, 88, 28, 91, 50, 40, 16,
						22, 99, 92, 79, 87, 51, 21, 77, 74, 77, 7, 42, 38, 42, 74, 83, 2, 5 },
				{ 46, 19, 77, 66, 24, 18, 5, 32, 2, 84, 31, 99, 92, 58, 96, 72, 91, 36, 62, 99, 55, 29, 53, 42, 12, 37,
						26, 58, 89, 50, 66, 19, 82, 75, 12, 48, 24, 87, 91, 85, 2, 7, 3, 76, 86 },
				{ 99, 98, 84, 93, 7, 17, 33, 61, 92, 20, 66, 60, 24, 66, 40, 30, 67, 5, 37, 29, 24, 96, 3, 27, 70, 62,
						13, 4, 45, 47, 59, 88, 43, 20, 66, 15, 46, 92, 30, 4, 71, 66, 78, 70, 53, 99 },
				{ 67, 60, 38, 6, 88, 4, 17, 72, 10, 99, 71, 7, 42, 25, 54, 5, 26, 64, 91, 50, 45, 71, 6, 30, 67, 48, 69,
						82, 8, 56, 80, 67, 18, 46, 66, 63, 1, 20, 8, 80, 47, 7, 91, 16, 3, 79, 87 },
				{ 18, 54, 78, 49, 80, 48, 77, 40, 68, 23, 60, 88, 58, 80, 33, 57, 11, 69, 55, 53, 64, 2, 94, 49, 60, 92,
						16, 35, 81, 21, 82, 96, 25, 24, 96, 18, 2, 5, 49, 3, 50, 77, 6, 32, 84, 27, 18, 38 },
				{ 68, 1, 50, 4, 3, 21, 42, 94, 53, 24, 89, 5, 92, 26, 52, 36, 68, 11, 85, 1, 4, 42, 2, 45, 15, 6, 50, 4,
						53, 73, 25, 74, 81, 88, 98, 21, 67, 84, 79, 97, 99, 20, 95, 4, 40, 46, 2, 58, 87 },
				{ 94, 10, 2, 78, 88, 52, 21, 3, 88, 60, 6, 53, 49, 71, 20, 91, 12, 65, 7, 49, 21, 22, 11, 41, 58, 99,
						36, 16, 9, 48, 17, 24, 52, 36, 23, 15, 72, 16, 84, 56, 2, 99, 43, 76, 81, 71, 29, 39, 49, 17 },
				{ 64, 39, 59, 84, 86, 16, 17, 66, 3, 9, 43, 6, 64, 18, 63, 29, 68, 6, 23, 7, 87, 14, 26, 35, 17, 12, 98,
						41, 53, 64, 78, 18, 98, 27, 28, 84, 80, 67, 75, 62, 10, 11, 76, 90, 54, 10, 5, 54, 41, 39, 66 },
				{ 43, 83, 18, 37, 32, 31, 52, 29, 95, 47, 8, 76, 35, 11, 4, 53, 35, 43, 34, 10, 52, 57, 12, 36, 20, 39,
						40, 55, 78, 44, 7, 31, 38, 26, 8, 15, 56, 88, 86, 1, 52, 62, 10, 24, 32, 5, 60, 65, 53, 28, 57,
						99 },
				{ 03, 50, 3, 52, 7, 73, 49, 92, 66, 80, 1, 46, 8, 67, 25, 36, 73, 93, 7, 42, 25, 53, 13, 96, 76, 83, 87,
						90, 54, 89, 78, 22, 78, 91, 73, 51, 69, 9, 79, 94, 83, 53, 9, 40, 69, 62, 10, 79, 49, 47, 3, 81,
						30 },
				{ 71, 54, 73, 33, 51, 76, 59, 54, 79, 37, 56, 45, 84, 17, 62, 21, 98, 69, 41, 95, 65, 24, 39, 37, 62, 3,
						24, 48, 54, 64, 46, 82, 71, 78, 33, 67, 9, 16, 96, 68, 52, 74, 79, 68, 32, 21, 13, 78, 96, 60,
						9, 69, 20, 36 },
				{ 73, 26, 21, 44, 46, 38, 17, 83, 65, 98, 7, 23, 52, 46, 61, 97, 33, 13, 60, 31, 70, 15, 36, 77, 31, 58,
						56, 93, 75, 68, 21, 36, 69, 53, 90, 75, 25, 82, 39, 50, 65, 94, 29, 30, 11, 33, 11, 13, 96, 2,
						56, 47, 7, 49, 2 },
				{ 76, 46, 73, 30, 10, 20, 60, 70, 14, 56, 34, 26, 37, 39, 48, 24, 55, 76, 84, 91, 39, 86, 95, 61, 50,
						14, 53, 93, 64, 67, 37, 31, 10, 84, 42, 70, 48, 20, 10, 72, 60, 61, 84, 79, 69, 65, 99, 73, 89,
						25, 85, 48, 92, 56, 97, 16 },
				{ 03, 14, 80, 27, 22, 30, 44, 27, 67, 75, 79, 32, 51, 54, 81, 29, 65, 14, 19, 4, 13, 82, 4, 91, 43, 40,
						12, 52, 29, 99, 7, 76, 60, 25, 1, 7, 61, 71, 37, 92, 40, 47, 99, 66, 57, 1, 43, 44, 22, 40, 53,
						53, 9, 69, 26, 81, 7 },
				{ 49, 80, 56, 90, 93, 87, 47, 13, 75, 28, 87, 23, 72, 79, 32, 18, 27, 20, 28, 10, 37, 59, 21, 18, 70, 4,
						79, 96, 3, 31, 45, 71, 81, 6, 14, 18, 17, 5, 31, 50, 92, 79, 23, 47, 9, 39, 47, 91, 43, 54, 69,
						47, 42, 95, 62, 46, 32, 85 },
				{ 37, 18, 62, 85, 87, 28, 64, 5, 77, 51, 47, 26, 30, 65, 5, 70, 65, 75, 59, 80, 42, 52, 25, 20, 44, 10,
						92, 17, 71, 95, 52, 14, 77, 13, 24, 55, 11, 65, 26, 91, 1, 30, 63, 15, 49, 48, 41, 17, 67, 47,
						3, 68, 20, 90, 98, 32, 4, 40, 68 },
				{ 90, 51, 58, 60, 6, 55, 23, 68, 5, 19, 76, 94, 82, 36, 96, 43, 38, 90, 87, 28, 33, 83, 5, 17, 70, 83,
						96, 93, 6, 4, 78, 47, 80, 6, 23, 84, 75, 23, 87, 72, 99, 14, 50, 98, 92, 38, 90, 64, 61, 58, 76,
						94, 36, 66, 87, 80, 51, 35, 61, 38 },
				{ 57, 95, 64, 6, 53, 36, 82, 51, 40, 33, 47, 14, 7, 98, 78, 65, 39, 58, 53, 6, 50, 53, 4, 69, 40, 68,
						36, 69, 75, 78, 75, 60, 3, 32, 39, 24, 74, 47, 26, 90, 13, 40, 44, 71, 90, 76, 51, 24, 36, 50,
						25, 45, 70, 80, 61, 80, 61, 43, 90, 64, 11 },
				{ 18, 29, 86, 56, 68, 42, 79, 10, 42, 44, 30, 12, 96, 18, 23, 18, 52, 59, 2, 99, 67, 46, 60, 86, 43, 38,
						55, 17, 44, 93, 42, 21, 55, 14, 47, 34, 55, 16, 49, 24, 23, 29, 96, 51, 55, 10, 46, 53, 27, 92,
						27, 46, 63, 57, 30, 65, 43, 27, 21, 20, 24, 83 },
				{ 81, 72, 93, 19, 69, 52, 48, 1, 13, 83, 92, 69, 20, 48, 69, 59, 20, 62, 5, 42, 28, 89, 90, 99, 32, 72,
						84, 17, 8, 87, 36, 3, 60, 31, 36, 36, 81, 26, 97, 36, 48, 54, 56, 56, 27, 16, 91, 8, 23, 11, 87,
						99, 33, 47, 2, 14, 44, 73, 70, 99, 43, 35, 33 },
				{ 90, 56, 61, 86, 56, 12, 70, 59, 63, 32, 1, 15, 81, 47, 71, 76, 95, 32, 65, 80, 54, 70, 34, 51, 40, 45,
						33, 4, 64, 55, 78, 68, 88, 47, 31, 47, 68, 87, 3, 84, 23, 44, 89, 72, 35, 8, 31, 76, 63, 26, 90,
						85, 96, 67, 65, 91, 19, 14, 17, 86, 4, 71, 32, 95 },
				{ 37, 13, 4, 22, 64, 37, 37, 28, 56, 62, 86, 33, 7, 37, 10, 44, 52, 82, 52, 6, 19, 52, 57, 75, 90, 26,
						91, 24, 6, 21, 14, 67, 76, 30, 46, 14, 35, 89, 89, 41, 3, 64, 56, 97, 87, 63, 22, 34, 3, 79, 17,
						45, 11, 53, 25, 56, 96, 61, 23, 18, 63, 31, 37, 37, 47 },
				{ 77, 23, 26, 70, 72, 76, 77, 4, 28, 64, 71, 69, 14, 85, 96, 54, 95, 48, 6, 62, 99, 83, 86, 77, 97, 75,
						71, 66, 30, 19, 57, 90, 33, 1, 60, 61, 14, 12, 90, 99, 32, 77, 56, 41, 18, 14, 87, 49, 10, 14,
						90, 64, 18, 50, 21, 74, 14, 16, 88, 5, 45, 73, 82, 47, 74, 44 },
				{ 22, 97, 41, 13, 34, 31, 54, 61, 56, 94, 3, 24, 59, 27, 98, 77, 4, 9, 37, 40, 12, 26, 87, 9, 71, 70, 7,
						18, 64, 57, 80, 21, 12, 71, 83, 94, 60, 39, 73, 79, 73, 19, 97, 32, 64, 29, 41, 7, 48, 84, 85,
						67, 12, 74, 95, 20, 24, 52, 41, 67, 56, 61, 29, 93, 35, 72, 69 },
				{ 72, 23, 63, 66, 1, 11, 7, 30, 52, 56, 95, 16, 65, 26, 83, 90, 50, 74, 60, 18, 16, 48, 43, 77, 37, 11,
						99, 98, 30, 94, 91, 26, 62, 73, 45, 12, 87, 73, 47, 27, 1, 88, 66, 99, 21, 41, 95, 80, 2, 53,
						23, 32, 61, 48, 32, 43, 43, 83, 14, 66, 95, 91, 19, 81, 80, 67, 25, 88 },
				{ 8, 62, 32, 18, 92, 14, 83, 71, 37, 96, 11, 83, 39, 99, 5, 16, 23, 27, 10, 67, 2, 25, 44, 11, 55, 31,
						46, 64, 41, 56, 44, 74, 26, 81, 51, 31, 45, 85, 87, 9, 81, 95, 22, 28, 76, 69, 46, 48, 64, 87,
						67, 76, 27, 89, 31, 11, 74, 16, 62, 3, 60, 94, 42, 47, 9, 34, 94, 93, 72 },
				{ 56, 18, 90, 18, 42, 17, 42, 32, 14, 86, 6, 53, 33, 95, 99, 35, 29, 15, 44, 20, 49, 59, 25, 54, 34, 59,
						84, 21, 23, 54, 35, 90, 78, 16, 93, 13, 37, 88, 54, 19, 86, 67, 68, 55, 66, 84, 65, 42, 98, 37,
						87, 56, 33, 28, 58, 38, 28, 38, 66, 27, 52, 21, 81, 15, 8, 22, 97, 32, 85, 27 },
				{ 91, 53, 40, 28, 13, 34, 91, 25, 1, 63, 50, 37, 22, 49, 71, 58, 32, 28, 30, 18, 68, 94, 23, 83, 63, 62,
						94, 76, 80, 41, 90, 22, 82, 52, 29, 12, 18, 56, 10, 8, 35, 14, 37, 57, 23, 65, 67, 40, 72, 39,
						93, 39, 70, 89, 40, 34, 7, 46, 94, 22, 20, 5, 53, 64, 56, 30, 5, 56, 61, 88, 27 },
				{ 23, 95, 11, 12, 37, 69, 68, 24, 66, 10, 87, 70, 43, 50, 75, 7, 62, 41, 83, 58, 95, 93, 89, 79, 45, 39,
						2, 22, 5, 22, 95, 43, 62, 11, 68, 29, 17, 40, 26, 44, 25, 71, 87, 16, 70, 85, 19, 25, 59, 94,
						90, 41, 41, 80, 61, 70, 55, 60, 84, 33, 95, 76, 42, 63, 15, 9, 3, 40, 38, 12, 3, 32 },
				{ 9, 84, 56, 80, 61, 55, 85, 97, 16, 94, 82, 94, 98, 57, 84, 30, 84, 48, 93, 90, 71, 5, 95, 90, 73, 17,
						30, 98, 40, 64, 65, 89, 7, 79, 9, 19, 56, 36, 42, 30, 23, 69, 73, 72, 7, 5, 27, 61, 24, 31, 43,
						48, 71, 84, 21, 28, 26, 65, 65, 59, 65, 74, 77, 20, 10, 81, 61, 84, 95, 8, 52, 23, 70 },
				{ 47, 81, 28, 9, 98, 51, 67, 64, 35, 51, 59, 36, 92, 82, 77, 65, 80, 24, 72, 53, 22, 7, 27, 10, 21, 28,
						30, 22, 48, 82, 80, 48, 56, 20, 14, 43, 18, 25, 50, 95, 90, 31, 77, 8, 9, 48, 44, 80, 90, 22,
						93, 45, 82, 17, 13, 96, 25, 26, 8, 73, 34, 99, 6, 49, 24, 6, 83, 51, 40, 14, 15, 10, 25, 1 },
				{ 54, 25, 10, 81, 30, 64, 24, 74, 75, 80, 36, 75, 82, 60, 22, 69, 72, 91, 45, 67, 3, 62, 79, 54, 89, 74,
						44, 83, 64, 96, 66, 73, 44, 30, 74, 50, 37, 5, 9, 97, 70, 1, 60, 46, 37, 91, 39, 75, 75, 18, 58,
						52, 72, 78, 51, 81, 86, 52, 8, 97, 1, 46, 43, 66, 98, 62, 81, 18, 70, 93, 73, 8, 32, 46, 34 },
				{ 96, 80, 82, 7, 59, 71, 92, 53, 19, 20, 88, 66, 3, 26, 26, 10, 24, 27, 50, 82, 94, 73, 63, 8, 51, 33,
						22, 45, 19, 13, 58, 33, 90, 15, 22, 50, 36, 13, 55, 6, 35, 47, 82, 52, 33, 61, 36, 27, 28, 46,
						98, 14, 73, 20, 73, 32, 16, 26, 80, 53, 47, 66, 76, 38, 94, 45, 2, 1, 22, 52, 47, 96, 64, 58,
						52, 39 },
				{ 88, 46, 23, 39, 74, 63, 81, 64, 20, 90, 33, 33, 76, 55, 58, 26, 10, 46, 42, 26, 74, 74, 12, 83, 32,
						43, 9, 2, 73, 55, 86, 54, 85, 34, 28, 23, 29, 79, 91, 62, 47, 41, 82, 87, 99, 22, 48, 90, 20, 5,
						96, 75, 95, 4, 43, 28, 81, 39, 81, 1, 28, 42, 78, 25, 39, 77, 90, 57, 58, 98, 17, 36, 73, 22,
						63, 74, 51 },
				{ 29, 39, 74, 94, 95, 78, 64, 24, 38, 86, 63, 87, 93, 6, 70, 92, 22, 16, 80, 64, 29, 52, 20, 27, 23, 50,
						14, 13, 87, 15, 72, 96, 81, 22, 8, 49, 72, 30, 70, 24, 79, 31, 16, 64, 59, 21, 89, 34, 96, 91,
						48, 76, 43, 53, 88, 1, 57, 80, 23, 81, 90, 79, 58, 1, 80, 87, 17, 99, 86, 90, 72, 63, 32, 69,
						14, 28, 88, 69 },
				{ 37, 17, 71, 95, 56, 93, 71, 35, 43, 45, 4, 98, 92, 94, 84, 96, 11, 30, 31, 27, 31, 60, 92, 3, 48, 5,
						98, 91, 86, 94, 35, 90, 90, 8, 48, 19, 33, 28, 68, 37, 59, 26, 65, 96, 50, 68, 22, 7, 9, 49, 34,
						31, 77, 49, 43, 6, 75, 17, 81, 87, 61, 79, 52, 26, 27, 72, 29, 50, 7, 98, 86, 1, 17, 10, 46, 64,
						24, 18, 56 },
				{ 51, 30, 25, 94, 88, 85, 79, 91, 40, 33, 63, 84, 49, 67, 98, 92, 15, 26, 75, 19, 82, 5, 18, 78, 65, 93,
						61, 48, 91, 43, 59, 41, 70, 51, 22, 15, 92, 81, 67, 91, 46, 98, 11, 11, 65, 31, 66, 10, 98, 65,
						83, 21, 5, 56, 5, 98, 73, 67, 46, 74, 69, 34, 8, 30, 5, 52, 7, 98, 32, 95, 30, 94, 65, 50, 24,
						63, 28, 81, 99, 57 },
				{ 19, 23, 61, 36, 9, 89, 71, 98, 65, 17, 30, 29, 89, 26, 79, 74, 94, 11, 44, 48, 97, 54, 81, 55, 39, 66,
						69, 45, 28, 47, 13, 86, 15, 76, 74, 70, 84, 32, 36, 33, 79, 20, 78, 14, 41, 47, 89, 28, 81, 5,
						99, 66, 81, 86, 38, 26, 6, 25, 13, 60, 54, 55, 23, 53, 27, 5, 89, 25, 23, 11, 13, 54, 59, 54,
						56, 34, 16, 24, 53, 44, 6 },
				{ 13, 40, 57, 72, 21, 15, 60, 8, 4, 19, 11, 98, 34, 45, 9, 97, 86, 71, 3, 15, 56, 19, 15, 44, 97, 31,
						90, 4, 87, 87, 76, 8, 12, 30, 24, 62, 84, 28, 12, 85, 82, 53, 99, 52, 13, 94, 6, 65, 97, 86, 9,
						50, 94, 68, 69, 74, 30, 67, 87, 94, 63, 7, 78, 27, 80, 36, 69, 41, 6, 92, 32, 78, 37, 82, 30, 5,
						18, 87, 99, 72, 19, 99 },
				{ 44, 20, 55, 77, 69, 91, 27, 31, 28, 81, 80, 27, 2, 7, 97, 23, 95, 98, 12, 25, 75, 29, 47, 71, 7, 47,
						78, 39, 41, 59, 27, 76, 13, 15, 66, 61, 68, 35, 69, 86, 16, 53, 67, 63, 99, 85, 41, 56, 8, 28,
						33, 40, 94, 76, 90, 85, 31, 70, 24, 65, 84, 65, 99, 82, 19, 25, 54, 37, 21, 46, 33, 2, 52, 99,
						51, 33, 26, 4, 87, 2, 8, 18, 96 },
				{ 54, 42, 61, 45, 91, 6, 64, 79, 80, 82, 32, 16, 83, 63, 42, 49, 19, 78, 65, 97, 40, 42, 14, 61, 49, 34,
						4, 18, 25, 98, 59, 30, 82, 72, 26, 88, 54, 36, 21, 75, 3, 88, 99, 53, 46, 51, 55, 78, 22, 94,
						34, 40, 68, 87, 84, 25, 30, 76, 25, 8, 92, 84, 42, 61, 40, 38, 9, 99, 40, 23, 29, 39, 46, 55,
						10, 90, 35, 84, 56, 70, 63, 23, 91, 39 },
				{ 52, 92, 3, 71, 89, 7, 9, 37, 68, 66, 58, 20, 44, 92, 51, 56, 13, 71, 79, 99, 26, 37, 2, 6, 16, 67, 36,
						52, 58, 16, 79, 73, 56, 60, 59, 27, 44, 77, 94, 82, 20, 50, 98, 33, 9, 87, 94, 37, 40, 83, 64,
						83, 58, 85, 17, 76, 53, 2, 83, 52, 22, 27, 39, 20, 48, 92, 45, 21, 9, 42, 24, 23, 12, 37, 52,
						28, 50, 78, 79, 20, 86, 62, 73, 20, 59 },
				{ 54, 96, 80, 15, 91, 90, 99, 70, 10, 9, 58, 90, 93, 50, 81, 99, 54, 38, 36, 10, 30, 11, 35, 84, 16, 45,
						82, 18, 11, 97, 36, 43, 96, 79, 97, 65, 40, 48, 23, 19, 17, 31, 64, 52, 65, 65, 37, 32, 65, 76,
						99, 79, 34, 65, 79, 27, 55, 33, 3, 1, 33, 27, 61, 28, 66, 8, 4, 70, 49, 46, 48, 83, 1, 45, 19,
						96, 13, 81, 14, 21, 31, 79, 93, 85, 50, 5 },
				{ 92, 92, 48, 84, 59, 98, 31, 53, 23, 27, 15, 22, 79, 95, 24, 76, 5, 79, 16, 93, 97, 89, 38, 89, 42, 83,
						2, 88, 94, 95, 82, 21, 1, 97, 48, 39, 31, 78, 9, 65, 50, 56, 97, 61, 1, 7, 65, 27, 21, 23, 14,
						15, 80, 97, 44, 78, 49, 35, 33, 45, 81, 74, 34, 5, 31, 57, 9, 38, 94, 7, 69, 54, 69, 32, 65, 68,
						46, 68, 78, 90, 24, 28, 49, 51, 45, 86, 35 },
				{ 41, 63, 89, 76, 87, 31, 86, 9, 46, 14, 87, 82, 22, 29, 47, 16, 13, 10, 70, 72, 82, 95, 48, 64, 58, 43,
						13, 75, 42, 69, 21, 12, 67, 13, 64, 85, 58, 23, 98, 9, 37, 76, 5, 22, 31, 12, 66, 50, 29, 99,
						86, 72, 45, 25, 10, 28, 19, 6, 90, 43, 29, 31, 67, 79, 46, 25, 74, 14, 97, 35, 76, 37, 65, 46,
						23, 82, 6, 22, 30, 76, 93, 66, 94, 17, 96, 13, 20, 72 },
				{ 63, 40, 78, 8, 52, 9, 90, 41, 70, 28, 36, 14, 46, 44, 85, 96, 24, 52, 58, 15, 87, 37, 5, 98, 99, 39,
						13, 61, 76, 38, 44, 99, 83, 74, 90, 22, 53, 80, 56, 98, 30, 51, 63, 39, 44, 30, 91, 91, 4, 22,
						27, 73, 17, 35, 53, 18, 35, 45, 54, 56, 27, 78, 48, 13, 69, 36, 44, 38, 71, 25, 30, 56, 15, 22,
						73, 43, 32, 69, 59, 25, 93, 83, 45, 11, 34, 94, 44, 39, 92 },
				{ 12, 36, 56, 88, 13, 96, 16, 12, 55, 54, 11, 47, 19, 78, 17, 17, 68, 81, 77, 51, 42, 55, 99, 85, 66,
						27, 81, 79, 93, 42, 65, 61, 69, 74, 14, 1, 18, 56, 12, 1, 58, 37, 91, 22, 42, 66, 83, 25, 19, 4,
						96, 41, 25, 45, 18, 69, 96, 88, 36, 93, 10, 12, 98, 32, 44, 83, 83, 4, 72, 91, 4, 27, 73, 7, 34,
						37, 71, 60, 59, 31, 1, 54, 54, 44, 96, 93, 83, 36, 4, 45 },
				{ 30, 18, 22, 20, 42, 96, 65, 79, 17, 41, 55, 69, 94, 81, 29, 80, 91, 31, 85, 25, 47, 26, 43, 49, 2, 99,
						34, 67, 99, 76, 16, 14, 15, 93, 8, 32, 99, 44, 61, 77, 67, 50, 43, 55, 87, 55, 53, 72, 17, 46,
						62, 25, 50, 99, 73, 5, 93, 48, 17, 31, 70, 80, 59, 9, 44, 59, 45, 13, 74, 66, 58, 94, 87, 73,
						16, 14, 85, 38, 74, 99, 64, 23, 79, 28, 71, 42, 20, 37, 82, 31, 23 },
				{ 51, 96, 39, 65, 46, 71, 56, 13, 29, 68, 53, 86, 45, 33, 51, 49, 12, 91, 21, 21, 76, 85, 2, 17, 98, 15,
						46, 12, 60, 21, 88, 30, 92, 83, 44, 59, 42, 50, 27, 88, 46, 86, 94, 73, 45, 54, 23, 24, 14, 10,
						94, 21, 20, 34, 23, 51, 4, 83, 99, 75, 90, 63, 60, 16, 22, 33, 83, 70, 11, 32, 10, 50, 29, 30,
						83, 46, 11, 5, 31, 17, 86, 42, 49, 1, 44, 63, 28, 60, 7, 78, 95, 40 },
				{ 44, 61, 89, 59, 4, 49, 51, 27, 69, 71, 46, 76, 44, 4, 9, 34, 56, 39, 15, 6, 94, 91, 75, 90, 65, 27,
						56, 23, 74, 6, 23, 33, 36, 69, 14, 39, 5, 34, 35, 57, 33, 22, 76, 46, 56, 10, 61, 65, 98, 9, 16,
						69, 4, 62, 65, 18, 99, 76, 49, 18, 72, 66, 73, 83, 82, 40, 76, 31, 89, 91, 27, 88, 17, 35, 41,
						35, 32, 51, 32, 67, 52, 68, 74, 85, 80, 57, 7, 11, 62, 66, 47, 22, 67 },
				{ 65, 37, 19, 97, 26, 17, 16, 24, 24, 17, 50, 37, 64, 82, 24, 36, 32, 11, 68, 34, 69, 31, 32, 89, 79,
						93, 96, 68, 49, 90, 14, 23, 4, 4, 67, 99, 81, 74, 70, 74, 36, 96, 68, 9, 64, 39, 88, 35, 54, 89,
						96, 58, 66, 27, 88, 97, 32, 14, 6, 35, 78, 20, 71, 6, 85, 66, 57, 2, 58, 91, 72, 5, 29, 56, 73,
						48, 86, 52, 9, 93, 22, 57, 79, 42, 12, 1, 31, 68, 17, 59, 63, 76, 7, 77 },
				{ 73, 81, 14, 13, 17, 20, 11, 9, 1, 83, 8, 85, 91, 70, 84, 63, 62, 77, 37, 7, 47, 1, 59, 95, 39, 69, 39,
						21, 99, 9, 87, 2, 97, 16, 92, 36, 74, 71, 90, 66, 33, 73, 73, 75, 52, 91, 11, 12, 26, 53, 5, 26,
						26, 48, 61, 50, 90, 65, 1, 87, 42, 47, 74, 35, 22, 73, 24, 26, 56, 70, 52, 5, 48, 41, 31, 18,
						83, 27, 21, 39, 80, 85, 26, 8, 44, 2, 71, 7, 63, 22, 5, 52, 19, 8, 20 },
				{ 17, 25, 21, 11, 72, 93, 33, 49, 64, 23, 53, 82, 3, 13, 91, 65, 85, 2, 40, 5, 42, 31, 77, 42, 5, 36, 6,
						54, 4, 58, 7, 76, 87, 83, 25, 57, 66, 12, 74, 33, 85, 37, 74, 32, 20, 69, 3, 97, 91, 68, 82, 44,
						19, 14, 89, 28, 85, 85, 80, 53, 34, 87, 58, 98, 88, 78, 48, 65, 98, 40, 11, 57, 10, 67, 70, 81,
						60, 79, 74, 72, 97, 59, 79, 47, 30, 20, 54, 80, 89, 91, 14, 5, 33, 36, 79, 39 },
				{ 60, 85, 59, 39, 60, 7, 57, 76, 77, 92, 6, 35, 15, 72, 23, 41, 45, 52, 95, 18, 64, 79, 86, 53, 56, 31,
						69, 11, 91, 31, 84, 50, 44, 82, 22, 81, 41, 40, 30, 42, 30, 91, 48, 94, 74, 76, 64, 58, 74, 25,
						96, 57, 14, 19, 3, 99, 28, 83, 15, 75, 99, 1, 89, 85, 79, 50, 3, 95, 32, 67, 44, 8, 7, 41, 62,
						64, 29, 20, 14, 76, 26, 55, 48, 71, 69, 66, 19, 72, 44, 25, 14, 1, 48, 74, 12, 98, 7 },
				{ 64, 66, 84, 24, 18, 16, 27, 48, 20, 14, 47, 69, 30, 86, 48, 40, 23, 16, 61, 21, 51, 50, 26, 47, 35,
						33, 91, 28, 78, 64, 43, 68, 4, 79, 51, 8, 19, 60, 52, 95, 6, 68, 46, 86, 35, 97, 27, 58, 4, 65,
						30, 58, 99, 12, 12, 75, 91, 39, 50, 31, 42, 64, 70, 4, 46, 7, 98, 73, 98, 93, 37, 89, 77, 91,
						64, 71, 64, 65, 66, 21, 78, 62, 81, 74, 42, 20, 83, 70, 73, 95, 78, 45, 92, 27, 34, 53, 71,
						15 },
				{ 30, 11, 85, 31, 34, 71, 13, 48, 5, 14, 44, 3, 19, 67, 23, 73, 19, 57, 6, 90, 94, 72, 57, 69, 81, 62,
						59, 68, 88, 57, 55, 69, 49, 13, 7, 87, 97, 80, 89, 5, 71, 5, 5, 26, 38, 40, 16, 62, 45, 99, 18,
						38, 98, 24, 21, 26, 62, 74, 69, 4, 85, 57, 77, 35, 58, 67, 91, 79, 79, 57, 86, 28, 66, 34, 72,
						51, 76, 78, 36, 95, 63, 90, 8, 78, 47, 63, 45, 31, 22, 70, 52, 48, 79, 94, 15, 77, 61, 67, 68 },
				{ 23, 33, 44, 81, 80, 92, 93, 75, 94, 88, 23, 61, 39, 76, 22, 3, 28, 94, 32, 6, 49, 65, 41, 34, 18, 23,
						8, 47, 62, 60, 3, 63, 33, 13, 80, 52, 31, 54, 73, 43, 70, 26, 16, 69, 57, 87, 83, 31, 3, 93, 70,
						81, 47, 95, 77, 44, 29, 68, 39, 51, 56, 59, 63, 7, 25, 70, 7, 77, 43, 53, 64, 3, 94, 42, 95, 39,
						18, 1, 66, 21, 16, 97, 20, 50, 90, 16, 70, 10, 95, 69, 29, 6, 25, 61, 41, 26, 15, 59, 63,
						35 } };
		printTree(tree);
		System.out.println();

		int firstSum = 0;
		int secondSum = 0;

		for (int i = tree.length - 1; i > 0; i--) {
			for (int j = 0; j < tree[i].length - 1; j++) {
				firstSum = tree[i][j] + tree[i - 1][j];
				secondSum = tree[i][j + 1] + tree[i - 1][j];
				tree[i - 1][j] = Math.max(firstSum, secondSum);
			}
		}

		printTree(tree);
		System.out.println();

		System.out.println("Max sum is: " + tree[0][0]);
	}
}