Java || DP || 5ms
Intuition\n Describe your first thoughts on how to solve this problem. \nuse DP algorithm to solve the problem\n\n# Approach\n Describe your approach to solving
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nuse DP algorithm to solve the problem\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. for the direction from right to left, create the 2D-array dp, dp1[r][i] represents that the number of continous 1s from right to the index i (must including [r][i]).\n2. for the direction from bottom to top, create the 2D-array dp, dp2[i][C] represents that the number of continous 1s from botoom to the index i (must including (i)[c])\n3. from above dp1 and dp2, it\'s easy to know the min number (minLen) of continous 1s from right to left and from bottom to top at index [r][c].\n4. check the index from (r + 0 to r + minLen - 1, and c + 0 to c + minLen -1), check at those index, if dp1 and dp2 equal or greaten than minLen,  those if there exist square that all boards are 1s, count the elements of that square.\n5. compare the max and current elements, get max number of elements\n6. return the results\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(m*n*min(m,n)),\nmin(m,n) means the min number of coninuous 1s from every direction\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n*m)\n\n# Code\n```\nclass Solution {\n  public int largest1BorderedSquare(int[][] grid) {\n        boolean exist1s = false;\n        for (int i = 0; i < grid.length; i ++) {\n            for (int j = 0; j < grid[0].length; j ++) {\n                if (grid[i][j] == 1) {\n                    exist1s = true;\n                    break;\n                }\n            }\n        }\n        if (!exist1s) {\n            return 0;\n        }\n        int row = grid.length;\n        int col = grid[0].length;\n        int max = 0;\n        //check the continues 1s from right to left\n        int[][] dp1 = new int[grid.length][grid[0].length];\n        for (int i = 0; i < row; i ++) {\n            dp1[i][col - 1] = grid[i][col - 1] == 1 ? 1 : 0; \n            for(int j = col - 2; j >=0; j --) {\n                if (grid[i][j] == 1) {\n                    dp1[i][j] = dp1[i][j + 1] + 1;\n                } else {\n                    dp1[i][j] = 0;\n                }\n            }\n        }\n        //check the number of continue 1s from bottom to top\n        int[][] dp2 = new int[row][col];\n        for (int i = 0; i < col; i ++) {\n            dp2[row -1][i] = grid[row - 1][i] == 1?  1: 0;\n            for (int j = row - 2; j >=0; j --) {\n                if(grid[j][i] == 1) {\n                    dp2[j][i] = dp2[j +1][i] + 1;\n                } else {\n                    dp2[j][i] = 0;\n                }\n            }\n        }\n\n        for(int r = 0; r < row; r ++) {\n            for (int c = 0; c < col; c ++) {\n                if(grid[r][c] == 1) {\n                    int minLen = Math.min(dp1[r][c], dp2[r][c]);\n                    for (int k = minLen; k > 0; k --) {\n                        if(dp2[r][c + k -1] >= k && dp1[r + k - 1][c] >= k) {\n                            int count = k * k;\n                            max = Math.max(max,count);\n                        }\n                    }\n                } \n            }\n        }\n        return max;\n    }\n}\n```
['Dynamic Programming', 'Java']