题目：
Given a non-empty 2D array grid of 0's and 1's, an island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.
Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)
Example 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]]Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.
Example 2:
[[0,0,0,0,0,0,0,0]]Given the above grid, return 0.
Note: The length of each dimension in the given grid does not exceed 50.
求连成一片的1的最大面积。很典型的dfs，基本上自己也能勉强摸索出来，对二维格子遍历，每个dfs，dfs里如果是0就return 0，如果是1就把它标记成0防止重复计算，然后上下左右分别继续dfs，把上下左右return的值相加最后return。刚开始判断上下左右边界条件的时候忘了有一边应该是grid[0].length导致错了……时间复杂度O(row * col)因为每个格子遍历了一遍，空间似乎没有用到额外的空间？
Runtime: 2 ms, faster than 99.66% of Java online submissions for Max Area of Island.
Memory Usage: 39.9 MB, less than 55.64% of Java online submissions for Max Area of Island.
class Solution { public int maxAreaOfIsland(int[][] grid) { int rows = grid.length; int cols = grid[0].length; int maxArea = 0; for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { int area = dfs(grid, i, j); maxArea = Math.max(area, maxArea); } } return maxArea; } private int dfs(int[][] grid, int i, int j) { if (grid[i][j] == 0) { return 0; } grid[i][j] = 0; int area = 1; if (i - 1 >= 0) { area += dfs(grid, i - 1, j); } if (i + 1 < grid.length) { area += dfs(grid, i + 1, j); } if (j - 1 >= 0) { area += dfs(grid, i, j - 1); } if (j + 1 < grid[0].length) { area += dfs(grid, i, j + 1); } return area; } }
