QUESTION:

给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为0。)

示例 1:

[[0,0,1,0,0,0,0,1,0,0,0,0,0], [0,0,0,0,0,0,0,1,1,1,0,0,0], [0,1,1,0,1,0,0,0,0,0,0,0,0], [0,1,0,0,1,1,0,0,1,0,1,0,0], [0,1,0,0,1,1,0,0,1,1,1,0,0], [0,0,0,0,0,0,0,0,0,0,1,0,0], [0,0,0,0,0,0,0,1,1,1,0,0,0], [0,0,0,0,0,0,0,1,1,0,0,0,0]] 对于上面这个给定矩阵应返回 6。注意答案不应该是11，因为岛屿只能包含水平或垂直的四个方向的‘1’。

示例 2:

[[0,0,0,0,0,0,0,0]] 对于上面这个给定的矩阵, 返回 0。

注意: 给定的矩阵grid 的长度和宽度都不超过 50。

EXPLANATION:

发现其实头条的很多问题并不是直接考虑的算法问题，而是将算法和实际问题结合在一起，自己需要去将实际问题抽象成算法问题最后再写出代码。
首先说一下思路：正常我们开始算的话应该是遍历如果遇到1的话，那么就需要观察他的前后左右，如果前后左右都有的话，就需要先算出先后左右的结果，然后加上本身的1，那么就是最终的结果了。
抽象成算法就是：
1.创建一个二维的boolean类型数组，用以标记已经计算了的1，并且放置首尾循环
2.遍历数组，遇到1并且没有进行标记，那么就开始计算这个[i,j]对应的值，也就是他的前后左右的结果
3.如果前后左右同样还有1，那么就可以进行递归遍历，重复2-3步骤
4.[i,j]处的结果就是 left+right+top+bottom的结果
5.利用了boolean的二维数组，可以有效的减少重复计算的问题

SOLUTION:

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        boolean[][] alreadyCount = new boolean[grid.length][grid[0].length];
        int result  = 0;
        for(int i = 0;i<grid.length;i++){
            for(int j = 0;j<grid[i].length;j++){
                if(grid[i][j]==1 && !alreadyCount[i][j]) result = Math.max(result,maxAreaOfIslandHelper(grid,alreadyCount,i,j));
            }
        }
        return result;
    }
    
    public static int maxAreaOfIslandHelper(int[][] grid,boolean[][] alreadyCount,int i,int j){
        if(i >=grid.length || i<0) return 0;
        if(j>=grid[0].length||j<0) return 0;
        if(alreadyCount[i][j] || grid[i][j]==0) return 0;
        alreadyCount[i][j] = true;
        int left = maxAreaOfIslandHelper(grid,alreadyCount,i,j-1);
        int right = maxAreaOfIslandHelper(grid,alreadyCount,i,j+1);
        int top = maxAreaOfIslandHelper(grid,alreadyCount,i-1,j);
        int bottom = maxAreaOfIslandHelper(grid,alreadyCount,i+1,j);
        return left+right+top+bottom+1;
    }
}