# simple, with an example

• ``````First, an example.
For the input: M[i,j]
[[0,1,1,0],
[0,1,1,0],
[0,0,0,1]]

The DP matrix would look like,  Mat[i,j,k] // k is always 4 ? since we only need up, left, leftd, rightd
[ [0,0,0,0],   [1,1,1,1],   [1,1,1,1],   [0,0,0,0] ],
[ [0,0,0,0],   [2,1,1,2],   [2,2,2,1],   [0,0,0,0] ],
[ [0,0,0,0],   [0,0,0,0],   [0,0,0,0],   [1,1,3,1] ]

For every cell [i,j], in the input matrix we save 4 items in dp matrix.
Take a look at cell [1, 1] in the given input matrix. We need to save
1. It has one 1 in the up direction, giving a total of 2 1s (including the 1 at cell [1,1])
2. It has zero 1 in the left direction, giving a total of 1 1 in that direction so far
3. It has zero 1 in the leftd direction, giving a total of 1 in that direction so far
4. It has one 1 in the rightd direction giving a total of 2 in that direction

That is why the cell in the dp matrix at the corresponding [1,1] shows [2,  1,     1,      2]
------------------------------------------------------------------------up, left, leftd, rightd

Why do we need to save 4 items for each cell?

Take a look at the cell [1,1] in the input matrix again.
If we blindly save that the longest 1s so far at cell [1,1] is 2 (because we have another 1 at the up position),
then what do you do when you come to cell [1,2] and find another 1?
Do you increment to 3 since you have 2 so far on the left of cell [1,2].
So, you are missing information there. You do not know if that 2 came from the up(no increment)
or left(should increment) side of cell [1,1].

So, just save all information from all 4 sides.
We do not need bottom, since we are going to calculate that when we iterate through matrix.
```Classic top-down DP```

Now, let's code

``````
``````public int LongestLine(int[,] M) {
int max = 0;
if (M == null) return max;

var m = M.GetLength(0); var n = M.GetLength(1);
var mat = new int[m, n, 4]; //every dp cell will now have 4 items

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < 4; k++) {
if (M[i, j] == 0) {
mat[i, j, k] = 0;
} else {
switch (k) {
case 0: // up
mat[i, j, k] = 1 + (i-1 < 0 ? 0 : mat[i - 1, j, k]);
break;
case 1: // left
mat[i, j, k] = 1 + (j-1 < 0 ? 0 : mat[i, j - 1, k]);
break;
case 2: // leftdiagonal
mat[i, j, k] = 1 + (j-1 < 0 || i-1 < 0 ? 0 : mat[i - 1, j - 1, k]);
break;
case 3: // rightdiagonal
mat[i, j, k] = 1 + (j+1 == n || i-1 < 0 ? 0 : mat[i - 1, j + 1, k]);
break;
}
max = mat[i, j, k] > max ? mat[i, j, k] : max;
}
}
}
}

return max;
}

``````

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