# Clean and easy 43ms O(mn) java code

• public class Solution {
int [][] map;
int [][] dp;
public int longestIncreasingPath(int[][] matrix) {
int m = matrix.length;
if(m < 1)
return 0;
int n = matrix[0].length;
map = new int [m + 2][n + 2];
dp = new int[m + 2][n + 2];
for(int i = 0; i < m; i ++) {
map[i + 1][0] = map[i + 1][n + 1] = 0x7fffffff;
dp[i + 1][0] = dp[i + 1][n + 1] = 0;
for(int j = 0; j < n; j ++) {
map[0][j + 1] = map[m + 1][j + 1] = 0x7fffffff;
dp[0][j + 1] = dp[m + 1][j + 1] = 0;
map[i + 1][j + 1] = matrix[i][j];
dp[i + 1][j + 1] = 0;
}
}
int ret = 0;
for(int i = 0; i < m; i ++)
for(int j = 0; j < n; j ++)
ret = Math.max(ret, dfs(i + 1, j + 1, m, n));
return ret;
}

public int dfs(int i, int j, int m, int n) {
if(i == 0 || j == 0 || i == m + 1 || j == n + 1)
return 0;
if(dp[i][j] > 0)
return dp[i][j];
int ret = 1;
if(map[i][j] > map[i - 1][j])
ret = Math.max(ret, dfs(i - 1, j, m, n) + 1);
if(map[i][j] > map[i + 1][j])
ret = Math.max(ret, dfs(i + 1, j, m, n) + 1);
if(map[i][j] > map[i][j - 1])
ret = Math.max(ret, dfs(i, j - 1, m, n) + 1);
if(map[i][j] > map[i][j + 1])
ret = Math.max(ret, dfs(i, j + 1, m, n) + 1);
dp[i][j] = ret;
return ret;
}

}

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