'''
keys: 
Solutions:
Similar:
T:
S:
'''
from typing import List

class Solution:
    # DP, T: O(m*n); S: O(m*n)
    def longestLine1(self, M: List[List[int]]) -> int:
        res = 0
        if not M: return res
        rows, cols = len(M), len(M[0])
        # cols + 2 since we have c+2 in the for loop
        # rows + 1 since we have r+1 in the for loop
        dp = [[[0]*4 for _ in range(cols + 2)] for _ in range(rows + 1)] 
        for r in range(rows):
            for c in range(cols):
                if M[r][c] == 1:
                    # horizontal, comparing with prev col
                    dp[r+1][c+1][0] = dp[r+1][c][0] + 1
                    res = max(res, dp[r+1][c+1][0])
                    # vertical, comparing with prev row
                    dp[r+1][c+1][1] = dp[r][c+1][1] + 1
                    res = max(res, dp[r+1][c+1][1])
                    # diagonal, comparing with prev upper-left val
                    dp[r+1][c+1][2] = dp[r][c][2] + 1
                    res = max(res, dp[r+1][c+1][2])
                    # anti-dia, comparing with prev upper-right val
                    dp[r+1][c+1][3] = dp[r][c+2][3] + 1
                    res = max(res, dp[r+1][c+1][3])
        return res
    
    
    # T: O(m*n); S: O(1)
    def longestLine(self, M: List[List[int]]) -> int:
        if not M: return 0
        rows, cols = len(M), len(M[0])
        
        ones = 0
        # horizontal 
        for r in range(rows):
            ct = 0
            for c in range(cols):
                if M[r][c] == 1:
                    ct += 1
                    ones = max(ones, ct)
                else:
                    ct = 0
        
        # vertical 
        for c in range(cols):
            ct = 0
            for r in range(rows):
                if M[r][c] == 1:
                    ct += 1
                    ones = max(ones, ct)
                else:
                    ct = 0
        
        # diagonal: increasing start from left cells then bottom cells
        for k in range(rows + cols):
            inc, desc = 0, 0
            r = min(k, rows - 1)
            c = max(0, k - rows)
            while r >= 0 and c < cols:
                if M[r][c] == 1:
                    inc += 1
                else:
                    inc = 0
                ones = max(ones, inc)
                r -= 1
                c += 1
        
            # antidiagonal: decreasing start from left cells then top cells
            r = max(rows - 1 - k, 0)
            c = max(0, k - rows)
            while r < rows and c < cols:
                if M[r][c] == 1:
                    desc += 1
                else:
                    desc = 0
                ones = max(ones, desc)
                r += 1
                c += 1
                
        return ones
        
        
        
        
        
        
        
        
        
        
        
        
        