Largest Square Subarray with Identical Elements

You are given an n × n matrix of integers. Your task is to identify the side length of the largest square subarray in which all elements are identical. This contiguous square block can appear anywhere in the matrix.

For example, if the whole matrix is filled with the same integer, then the largest square subarray has a side length equal to n. Otherwise, you need to determine the maximum side length k (1 ≤ k ≤ n) for which there exists a k × k submatrix where every element is the same.

You are recommended to use a dynamic programming approach to solve this problem efficiently.

inputFormat

The first line contains a single integer n (n ≥ 1), representing the size of the matrix.

The following n lines each contain n space-separated integers, representing the rows of the matrix.

outputFormat

Output a single integer denoting the side length of the largest square subarray in which all elements are identical.

5
1 1 1 1 1
1 1 1 1 1
1 1 1 0 0
1 1 1 0 0
1 1 1 0 0

3