Euler's Problem 18

if you have heard of Euler's Problems then you might be aware of the Site Euler.net.

We have the input array

3
7 4
2 4 6
8 5 9 3

This problem deals with getting a path from top to bottom of contiguous elements which has the highest sum.

The trick is to see from the bottom up, in this example take the second last row and calculate the sum with one element being this and second being the element directly below and diagonally adjacent.

So, for element 2 in row 3  would be :
2 + 8 = 10
2+5 = 7

So, we can narrow down that we can choose the max number out of the two options which will give us more sum value.

Now, after calculating this sum replace the Sum value in this case 10 in position of 2.

Similarly, we will have this at the end of iteration for row = 2

3
7 4
10 13 15

Hence the solution is : 3 7 4 9
Sum : 23

Here is the Java code for the same

package com.test.practise;

public class MaxInMatrix {
 
 private int[][] input;
 private int[] output;
 
 public MaxInMatrix(int[][] input){
  this.input = input;
  this.output = new int[input.length];
 }
 
 
  public void getPath(){
  output[0] = input[0][0];
  int row = input.length -2;
  int j = 0;
  while(row >= 0){
   for(j=0; j<= row; j++){
    input[row][j] += Math.max(input[row+1][j], input[row+1][j+1]);
   }
   row--;
  }
  
  
  System.out.println(" ");
  System.out.print("Total Sum of the path is: " + input[0][0]);
 }
 
 
 public static void main(String[] args) {
  int[][] input = {{3},{7,4},{2,4,6},{8,5,9,3}};
  MaxInMatrix obj = new MaxInMatrix(input);
  obj.getPath();
 }

}

Refernces:
Euler's Project : http://projecteuler.net