Java short dp AC solution


  • 1
    public class Solution {
        int[][] directions = { { 0, -1 }, { -1, -1 }, { -1, 0 }, { -1, 1 } };
        public int longestLine(int[][] matrix) {
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
                return 0;
            }
            int m = matrix.length;
            int n = matrix[0].length;
            int[][][] lengths = new int[m][n][4];
            int max = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (matrix[i][j] == 0) {
                        continue;
                    }
                    int k = 0;
                    for (int[] direction : directions) {
                        int row = i + direction[0];
                        int col = j + direction[1];
                        lengths[i][j][k] = row >= 0 && col >= 0 && col < n ? lengths[row][col][k] + 1 : 1;
                        max = Math.max(max, lengths[i][j][k]);
                        k++;
                    }
                }
            }
            return max;
        }
    }
    

Log in to reply
 

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