amazon set 1

Question 3: There is a N*N integer matrix Arr[N][N]. From the row r and
   column c, we can go to any of the following three indices:

   I.                Arr[ r+1 ][ c-1 ] (valid only if c-1>=0)

   II.               Arr[ r+1 ][ c ]

   III.              Arr[ r+1 ][ c+1 ] (valid only if c+1<=N-1)

   So if we start at any column index on row 0, what is the largest sum of
   any of the paths till row N-1.

 

int findLargestPath( int[N][N] Arr )
{
    int max = 0;
    for( int i = 0; i < N; i++ )
    {
        int temp = searchPath( Arr, i, 0 );
        if( max < temp )
        {
            max = temp;
        }
    }

    return max;
}

private int maxPath = 0;

int searchPath( int[N][N] Arr, int rowPos, int colPos, ArrayList<Integer> list )
{
    if( rowPos < N-1 )
    {
        for( int c = colPos -1; c < colPos+2; c++ )
        {
            if( c >= 0 && c < N )
            {
                list.add( Arr[rowPos+1][c];
                ArrayList<Integer> newList = list.clone();
                searchPath( Arr, rowPos+1, c, newList )
            }
        }
    }
    // already hit the bottom
    else if( rowPos == N -1 )
    {
        int sum = 0;
        for( int i : list )
        {
            sum += i;
        }
        if( maxPath < sum )
        {
            maxPath = sum;
        }
    }

    return maxPath;
}

Advertisements
This entry was posted in Uncategorized and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s