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


  • 0
    G
         /*
            (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;

Log in to reply
 

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