Фермер (Динамика, max квадрат из 1)

import java.io.*;
import java.math.BigInteger;
import java.util.*;

import static java.lang.Math.max;
import static java.lang.Math.min;

class Pair<A, B> {
    A fst;
    B snd;

    public Pair(A fst, B snd) {
        this.fst = fst;
        this.snd = snd;
    }

    public A getFst() {
        return fst;
    }

    public B getSnd() {
        return snd;
    }
}

public class Main {

    public static void main(String[] args) throws IOException {
        //Scanner sc = new Scanner(System.in);//new File("lis.in"));//System.in);
        BufferedReader bd = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(bd.readLine());

        String[] a = new String[n];
        for (int i = 0; i < n; i++) {
            a[i] = bd.readLine();
        }

        int[][] s = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++)
            {
                s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + (a[i - 1].charAt(j - 1) == '0' ? 0 : 1);
            }
        }

        long ans = 0;
        long currentSquareSum;
        for (int k = 1; k <= n; k++)
        {
            for (int r = 0; r < n - k + 1; r++)
            {
                for (int c = 0; c < n - k + 1; c++)
                {
                    currentSquareSum = s[r + k][c + k] - s[r + k][c] - s[r][c + k] + s[r][c];
                    if (k * k == currentSquareSum)
                        ans = currentSquareSum;
                }
            }
        }
        System.out.println(ans);
    }
}