> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/leetcode/dynamic-programming/562-longest-line-of-consecutive-one-in-matrix.md).

# 562  Longest Line of Consecutive One in Matrix

## 562. [Longest Line of Consecutive One in Matrix](https://leetcode.com/problems/longest-line-of-consecutive-one-in-matrix/description/)

## 1. Question

Given a 01 matrix **M**, find the longest line of consecutive one in the matrix. The line could be horizontal, vertical, diagonal or anti-diagonal.

**Example:**

```
Input:
[[0,1,1,0],
 [0,1,1,0],
 [0,0,0,1]]

Output: 3
```

**Hint:** The number of elements in the given matrix will not exceed 10,000.

## 2. Implementation

**(1) DP**

```java
public class Solution {
    public int longestLine(int[][] M) {
        if (M == null || M.length == 0) {
            return 0;
        }

        int m = M.length, n = M[0].length;
        int res = 0;

        // dp[i][j][0] means the longest consecutive 1 horizontally at (i, j)
        // dp[i][j][1] means the longest consecutive 1 vertically at (i, j)
        // dp[i][j][2] means the longest consecutive 1 diagnolly at (i, j)
        // dp[i][j][3] means the longest consecutive 1 anti-diagnolly (i, j)
        int[][][] dp = new int[m][n][4];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (M[i][j] == 1) {
                    // Horizontal
                    dp[i][j][0] = j > 0 ? dp[i][j - 1][0] + 1 : 1;
                    // Vertical
                    dp[i][j][1] = i > 0 ? dp[i - 1][j][1] + 1 : 1;
                    // Diagnol
                    dp[i][j][2] = (i > 0 && j > 0) ? dp[i - 1][j - 1][2] + 1 : 1;
                    // Anti-Diagnol
                    dp[i][j][3] = (i > 0 && j < n - 1) ? dp[i - 1][j + 1][3] + 1 : 1;
                    res = Math.max(res, Math.max(dp[i][j][0], dp[i][j][1]));
                    res = Math.max(res, Math.max(dp[i][j][2], dp[i][j][3]));
                }
            }
        }
        return res;
    }
}
```

## 3. Time & Space Complexity

**DP:** 时间复杂度O(mn), 空间复杂度O(mn)