Path in Matrix geeks solution java

Path in Matrix geeks solution java

  June 18, 2017    

---

Problem : Given a n*n  matrix Matrix[N][N] of positive integers.  There are only three possible moves from a cell Matrix[r][c].

1. Matrix[r+1][c]

2. Matrix[r+1][c-1]

3. Matrix[r+1][c+1]

Starting from any column in row 0, return the largest sum of any of the paths up to row N-1.

SOlution : Take maximum of cells that can be traversed from a cell .
Here when we got to 2nd row we are finding max for each cell that can be tracked and add that into current element and so on.
At last we are finding max and printing that.

import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
 {
     public static int max(int a,int b)
     {
         return (a>b)?a:b;
     }
     public static int max(int a,int b,int c)
     {
         int temp=max(a,b);
         return (temp>c)?temp:c;
     }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
   int n=ab.nextInt();
   int arr[][]=new int[n][n];
   for(int i=0;i<n;i++)
   for(int j=0;j<n;j++)
   {
   arr[i][j]=ab.nextInt();
   if(i>0)
   {
        if(j==0){
                   arr[i][j]+= max(arr[i-1][j], arr[i-1][j+1]);
               }
               else if(j==n-1){
                   arr[i][j]+=max(arr[i-1][j], arr[i-1][j-1]);
               }
               else{
                   arr[i][j]+= max(arr[i-1][j], arr[i-1][j-1], arr[i-1][j+1]);
               }
   }
     
   }
   int max=0;
   for(int i=0;i<n;i++){
       if(arr[n-1][i]>max)
       max=arr[n-1][i];
   }
   System.out.println(max);
}
}
}