Amazon SDE II Written Test

Recently I gave the test for Amazon on Hacker-Earth. Only 2 programming questions were asked-
1. Connected Cells in a Grid
Given,
Matrix with m rows and n columns each of which contains either 1 or 0.
Two cells are said to be connected if they are adjacent to each other horizontally, vertically or diagonally. The connected and filled cells from a region. There may be several regions in the matrix.
Find the number of cells in the largest region in the matrix.

Sample Input
4
4
1 1 0 0
0 1 1 0
0 0 1 0
1 0 0 0

Sample Output
5

Explaination
X X 0 0
0 X X 0
0 0 X 0
1 0 0 0
where X indicate the largest connected component.


Solution:

import java.util.Scanner;

public class AmazonTest {

    public static boolean[][] visited;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int M = sc.nextInt();
        int N = sc.nextInt();
        int[][] inputElement = new int[M][N];
        visited = new boolean[M][N];
        for(int i = 0; i < M; i++) {
            for(int j = 0; j < N; j++) {
                inputElement[i][j] = sc.nextInt();
                visited[i][j] = false;
            }
        }
        int max = 0;
        for(int i = 0; i < M; i++) {
            for(int j = 0; j < N; j++) {
                if(!visited[i][j]) max = Math.max(max, findZoneHelper(inputElement, i, j, 0, M, N));
            }
        }
        System.out.println(max);
        sc.close();
        
        
        
    }
    
    public static int findZoneHelper(int[][] grid, int i, int j, int count, int M, int N) {
        if(i < 0 || j < 0 || i >= M || j >= N) return 0;
        if(visited[i][j]) return 0;
        visited[i][j] = true;
        if(grid[i][j] == 0) return 0;
        else return 1 +
            findZoneHelper(grid, i-1, j-1, count, M, N) +
            findZoneHelper(grid, i-1, j, count, M, N) + 
            findZoneHelper(grid, i-1, j+1, count, M, N) + 
            findZoneHelper(grid, i, j-1, count, M, N) + 
            findZoneHelper(grid, i, j, count, M, N) + 
            findZoneHelper(grid, i, j+1, count, M, N) + 
            findZoneHelper(grid, i+1, j-1, count, M, N) + 
            findZoneHelper(grid, i+1, j, count, M, N) + 
            findZoneHelper(grid, i+1, j+1, count, M, N);
    }

} 

2. The Maximum Subarray
Given an array A of N elements, find the maximum possible sum of a

• Contiguous subarray
• Non-contiguoug subarray

Empty subarrays/sequences should not be considered.

Sample Input
2
4
1 2 3 4
6
2 -1 2 3 4 -5

Sample Output
10 10
10 11

Solution: http://ideone.com/XKz309