# My C++ DP solution using 2N space only, very easy to understand.

• ``````     /*
(1) We need to remember information from previous computation, so we need one extra vector to cache that result.
(2) The N+2 can be reduced to N, but using it make the code more readable.
*/
if (matrix.empty() || matrix[0].empty()) {
return 0;
}

const auto M = matrix.size();
const auto N = matrix[0].size();

vector<vector<int>> preRow(N+2, vector<int>(4,0));
vector<vector<int>> curRow(N+2, vector<int>(4,0));

int sol = 0;
for (auto i = 0; i < M; i++) {
for (auto j = 1; j <= N; j++) {
if (matrix[i][j-1] == 1) {
//from left to right
curRow[j][0] = curRow[j-1][0] + 1;
//from top to bottom
curRow[j][1] = preRow[j][1] + 1;
//for diagonal
curRow[j][2] = preRow[j-1][2] + 1;
//for antigonal
curRow[j][3] = preRow[j+1][3] + 1;
} else {
curRow[j][0] = 0;
curRow[j][1] = 0;
curRow[j][2] = 0;
curRow[j][3] = 0;
}
sol = max(sol, curRow[j][0]);
sol = max(sol, curRow[j][1]);
sol = max(sol, curRow[j][2]);
sol = max(sol, curRow[j][3]);
}
swap(preRow, curRow);
}
return sol;``````

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