# Java easy-to-understand O(m*n) solution

• If using the model of DP to treat this problem, your sub-problem is (for each cell): which line
( | , __ , \ , / ) gives the MAX (the direction of arrow totally depends on how you traverse your matrix). Treat each row as if this is the last row of your matrix, and use a 3d array ( int[m][n][4] ) to memoize the result. I saw @compton_scatter has similar idea, but I figured this out myself, and mine is probably little bit cleaner.
The memoized results of the example is shown below:

``````int[][] directions = new int[][]{{-1,-1},{-1,0},{0,-1},{-1,1}};

[0000][1111][1121][0000]
[0000][1212][2221][0000]
[0000][0000][0000][3111]
``````

My code:

``````    public int longestLine(int[][] M) {
int[][] directions = new int[][]{{-1,-1},{-1,0},{0,-1},{-1,1}};
if(M.length==0)return 0;
int[][][] memo = new int[M.length][M[0].length][4];
int res = 0;
for(int i=0;i<M.length;i++){
for(int j=0;j<M[0].length;j++){
if(M[i][j]==1){
for(int k=0;k<4;k++){
int r = i+directions[k][0], c = j+directions[k][1];
memo[i][j][k] = 1;
if(r>=0&&c>=0&&r<M.length&&c<M[0].length&&M[r][c]==1){
memo[i][j][k] += memo[r][c][k];
res = Math.max(res, memo[i][j][k]);
}
res = Math.max(res, memo[i][j][k]);
}
}
}
}
return res;
}
``````

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