Squares and shapes (DP — Grid Sub-pattern)

// dp[c + 1] (current row) = side of the largest all-1 square whose bottom-right corner is (r, c).
// It is 1 + min(top, left, top-left); top-left is saved in `diag` before it is overwritten.
int largestSquareSide(const vector<vector<char>>& g) {
    int m = g.size(), n = g[0].size(), best = 0;
    vector<int> dp(n + 1, 0);                        // dp[c + 1] is column c; dp[0] stays 0
    for (int r = 0; r < m; r++) {
        int diag = 0;                                // top-left of the cell being filled
        for (int c = 0; c < n; c++) {
            int top = dp[c + 1];                     // still the previous row's value
            dp[c + 1] = g[r][c] == '1' ? 1 + min({top, dp[c], diag}) : 0;
            diag = top;
            best = max(best, dp[c + 1]);             // sum dp[c + 1] instead to COUNT squares
        }
    }
    return best;                                     // the area is best * best
}