# DFS Solution 16 ms

• ``````public int longestIncreasingPath(int[][] matrix) {
if(matrix == null || matrix.length == 0 || matrix[0] == null){
return 0;
}

int[][] cache = new int[matrix.length][matrix[0].length];
int max = 0;
for(int i = 0; i < matrix.length; i++){
for(int j = 0; j < matrix[0].length; j++){
max = Math.max(max, longestIncreasingPath(i, j, null, cache, matrix));
}
}

return max;
}

private int longestIncreasingPath(int row, int column, Integer preNum, int[][] cache, int[][] matrix){
if(row < 0 || row >= matrix.length || column < 0 || column >= matrix[0].length){
return 0;
}

if(preNum != null && preNum >= matrix[row][column]){
return 0;
}
if(cache[row][column] != 0){
return cache[row][column];
}

preNum = matrix[row][column];
int up = longestIncreasingPath(row - 1, column, preNum,cache, matrix);
int down = longestIncreasingPath(row + 1, column, preNum, cache, matrix);
int left = longestIncreasingPath(row , column - 1, preNum, cache, matrix);
int right = longestIncreasingPath(row , column + 1, preNum, cache, matrix);
int localMax = Math.max(Math.max(up, down), Math.max(left, right)) + 1 ;
cache[row][column] = localMax;
return localMax;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.