Java simple prefix dp
\n    public int largest1BorderedSquare(int[][] g) {\n        int res = 0, m = g.length, n = g[0].length, dp[][][] = new int[m + 1][n + 1][2];\n        for (int
```\n    public int largest1BorderedSquare(int[][] g) {\n        int res = 0, m = g.length, n = g[0].length, dp[][][] = new int[m + 1][n + 1][2];\n        for (int i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                if (g[i][j] == 0) continue;\n                dp[i+1][j+1][0] += dp[i][j+1][0] + 1;\n                dp[i+1][j+1][1] += dp[i+1][j][1] + 1;\n                int pre = Math.min(dp[i+1][j+1][0], dp[i+1][j+1][1]);\n                if (pre <= res) continue;\n                for (int k = pre; k > res; k--) {\n                    if (dp[i + 1 - k + 1][j + 1][1] >= k && dp[i + 1][j + 1 - k + 1][0] >= k) {\n                        res = k;\n                        break;\n                    }\n                }\n            }\n        }\n        return res * res;\n    }\n```
[]