# DP Solution w/ Python & C++

• python solution, O(NM) time, O(NM) space

``````class Solution(object):
def longestLine(self, M):
"""
:type M: List[List[int]]
:rtype: int
"""
n, m, ll = len(M), len(M[0]) if M else 0, 0
dp = [[[0, 0, 0 ,0] for j in xrange(m + 2)] for i in xrange(n + 1)]
for i in xrange(n):
for j in xrange(m):
if M[i][j] == 1:
dp[i+1][j+1][0] = dp[i+1][j][0] + 1
dp[i+1][j+1][1] = dp[i][j][1] + 1
dp[i+1][j+1][2] = dp[i][j+1][2] + 1
dp[i+1][j+1][3] = dp[i][j+2][3] + 1
ll = max(ll, max(dp[i+1][j+1]))
return ll
``````

notice that we only need previous dp row, we can reduce it to O(N) space

``````class Solution(object):
def longestLine(self, M):
"""
:type M: List[List[int]]
:rtype: int
"""
n, m, ll = len(M), len(M[0]) if M else 0, 0
dp = [[[0, 0, 0 ,0] for j in xrange(m + 2)] for i in xrange(2)]
for i in xrange(n):
for j in xrange(m):
if M[i][j] == 1:
dp[1][j+1][0] = dp[1][j][0] + 1
dp[1][j+1][1] = dp[0][j][1] + 1
dp[1][j+1][2] = dp[0][j+1][2] + 1
dp[1][j+1][3] = dp[0][j+2][3] + 1
ll = max(ll, max(dp[1][j+1]))
dp[0], dp[1] = dp[1], dp[0]
for j in xrange(1, m + 1):
dp[1][j][:] = [0] * 4
return ll
``````

c++ solution

``````class Solution {
public:
int longestLine(vector<vector<int>>& M) {
int n = M.size(), m = n == 0 ? 0 : M[0].size(), ll = 0;
vector<int> pre(4 * m + 8), cur(4 * m + 8);
for ( int i = 0; i < n; ++i ) {
for ( int j = 0; j < m; ++j ) {
if ( M[i][j] ) {
cur[4 * j + 4] = cur[4 * j] + 1; // left
cur[4 * j + 5] = pre[4 * j + 1] + 1; // left top
cur[4 * j + 6] = pre[4 * j + 6] + 1; // top
cur[4 * j + 7] = pre[4 * j + 11] + 1; // right top
}
}
ll = max(ll, *max_element(cur.begin(), cur.end()));
pre = cur;
fill(cur.begin(), cur.end(), 0);
}
return ll;
}
};
``````

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