By starting at the top of the triangle below and moving to adjacent numbers
on the row below, the maximum total from top to bottom is 23.

   3
  7 4
 2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:

                75
               95 64
              17 47 82
            18 35 87 10
           20 04 82 47 65
          19 01 23 75 03 34
         88 02 77 73 07 63 67
        99 65 04 28 06 16 70 92
       41 41 26 56 83 40 80 70 33
      41 48 72 33 47 32 37 16 94 29
     53 71 44 65 25 43 91 52 97 51 14
    70 11 33 28 77 73 17 78 39 68 17 57
   91 71 52 38 17 14 91 43 58 50 27 29 48
  63 66 04 68 89 53 67 30 73 16 69 87 40 31
 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

public class Euler_18{
// A custom data structure used to store
// the array so that I can seperate the
// logic from the storage
static class TriangularArray{
    HashMap<Integer, int[]> map;
    int someInt;
    int size;
    // All the elements will be stored in
    // HashMap according to their order
    public TriangularArray(int size){
        this.size = size;
        map = new HashMap<Integer, int[]>();
        // Initialise the array
        for(int i=1; i<=size; i++){
            int[] currArray = new int[i];
            map.put(i, currArray);
        }
    }


    // Accept the array
    public void acceptArray(Scanner in){
        for(int i=1; i<=size; i++){
            int[] currArray = map.get(i);
            for(int j=0; j<currArray.length; j++){
                currArray[j] = in.nextInt();
            }
            map.put(i, currArray);
        }
    }


    // Display the array
    public void displayArray(){
        for(int i=1; i<=size; i++){
            int[] currArray = map.get(i);
            System.out.println("Array " + i + " : " + Arrays.toString(currArray));
        }
    }


    // Finds the maximum using Memoization.
    public void findMaximum(){
        for (int i=size-1; i>0; i--) {
            int[] currArray = map.get(i);
            int[] belowArray = map.get(i+1);
            for (int j=0; j<currArray.length; j++) {
                // The value of current element will be the maximum of the 2 values
                // of the array directly below it
                currArray[j] = Math.max(belowArray[j], belowArray[j+1]) + currArray[j];
            }
        }
        System.out.println("The maximum route is of length : " + map.get(1)[0]);
    }
}


public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int size = in.nextInt();
    TriangularArray theArray = new TriangularArray(size);
    theArray.acceptArray(in);
    theArray.displayArray();
    theArray.findMaximum();
}
}