2.3 Largest X of 1s

Assumptions: given matrix is not null, size n*m, n & m >= 0

Input: int [][] binary matrix

Output: int arm length of the largest X of 1s

Solution:

1. Similar to 2.2, maintain 4 ( → 2) directions to store longest consecutive 1s

2. This time, check diagonal positions

if index out of bound, dp[i][j] = 0

left -> right dp1[i][j] = dp[i - 1][j - 1] + 1 //top-left

right -> left dp2[i][j] = dp[i + 1][j + 1] + 1 //bottom-right

top -> bottom dp3[i][j] = dp[i - 1][j + 1] + 1 //top-right

bottom -> top dp4[i][j] = dp[i + 1][j - 1] + 1 //bottom-left

3. Merge into 2 int[][]