562. Longest Line of Consecutive One in Matrix (3D DP)

brute force:

T: O(mn)

S: O(1)

針對四種 case 去寫, 但 code 會太長,

有效計算對角線的座標:

https://www.cnblogs.com/grandyang/p/6900866.html

3-D DP

T: O(mn)

S: O(4mn)

class Solution {
    public int longestLine(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int[][][] dp = new int[m][n][4];
        
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) { // not 1
                    continue;
                }
                for (int k = 0; k < 4; k++) { // if 1, give dp[i][j] plus 1
                    dp[i][j][k] = 1;
                }
                if (j-1 >= 0) {
                    dp[i][j][0] += dp[i][j-1][0]; // horizon
                }
                if (i-1 >= 0) {
                    dp[i][j][1] += dp[i-1][j][1]; // vertical
                }
                if (i-1 >= 0 && j-1 >= 0) {
                    dp[i][j][2] += dp[i-1][j-1][2]; // diagno
                }
                if (i-1 >= 0 && j+1 < n) {
                    dp[i][j][3] += dp[i-1][j+1][3]; // anti-diagno
                }
                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;
    }
}