clean JAVA DP over 100% ! just to store the maximum possibility
The main trick here is to use two dp 2d array to respectively store the maximum left-side outreach point and top-side outreach point. \n\nBy using these two dp,
The main trick here is to use two dp 2d array to respectively store the maximum left-side outreach point and top-side outreach point. \n\nBy using these two dp, we can directly be inferred whether currenly possible length is valid or not. \n\nSo in the third for loop, we just need to test the current possible length step by step, from the maximum point to the closest. (Early stop when found the valid length helps to reduce time).\n\ngoelrishabh5\'s image might help you to understand the meaning of outreach point\nhttps://leetcode.com/problems/largest-1-bordered-square/discuss/345265/c%2B%2B-beats-100-(both-time-and-memory)-concise-with-algorithm-and-image\n\nPlease be free to leave any question~ GOOD LUCK\n```\nclass Solution {\n    public int largest1BorderedSquare(int[][] grid) {\n        if (grid.length==0) return 0;\n        int[][] dpr = new int[grid.length+1][grid[0].length+1];\n        int[][] dpc = new int[grid.length+1][grid[0].length+1];\n        int dist, max=0;\n        for (int r=1;r<=grid.length;r++){\n            for (int c=1;c<=grid[0].length;c++){\n                if (grid[r-1][c-1]==0) continue;\n                dpr[r][c] = dpr[r-1][c]+1;\n                dpc[r][c] = dpc[r][c-1]+1;\n                dist = Math.min(dpr[r][c],dpc[r][c]);\n                for (int i=dist;i>=1;i--){\n                    if (dpr[r][c-i+1]>=i \n                        && dpc[r-i+1][c]>=i){\n                        max = Math.max(max, i*i);\n                        break;\n                    }\n                }\n            }\n        }\n        return max;\n    }\n}\n```
[]