//-- https://www.geeksforgeeks.org/maximum-size-sub-matrix-with-all-1s-in-a-binary-matrix/?ref=lbp

​

//-- done by recurse, more optimal is by dynamic programming as per the link above

​

using System;

public class Program

{

    public static void Main()

    {

        var matrix = new int[,]

        {

            {0, 1, 1, 0, 1},

            {1, 1, 0, 1, 0},

            {0, 1, 1, 1, 0},

            {1, 1, 1, 1, 0},

            {1, 1, 1, 1, 1},

            {0, 0, 0, 0, 0}

        };

        var result = GetMaxSubMatrixSize(matrix);

        Console.WriteLine("Result: " + result);

    }

    private static int GetMaxSubMatrixSize(int [,] matrix)

    {

        var maxSize = 0;

        var lengthI = matrix.GetLength(0);

        var lengthJ = matrix.GetLength(1);

        for(var i = 0; i < lengthI; i++)

        for(var j = 0; j < lengthJ; j++)

        {

            if(matrix[i, j] != 1)

               continue;

            GetMaxSubMatrixSizeRecursive(matrix, i, j, 1, lengthI, lengthJ, ref maxSize);

        }

        return maxSize;

    }

    private static void GetMaxSubMatrixSizeRecursive(int[,] matrix, int startI, int startJ, int currentSize, int lengthI, int lengthJ, ref int maxSize)

    {

        if(startI + currentSize == lengthI)

            return;

        if(startJ + currentSize == lengthJ)

            return;

        for(var i = startI; i < currentSize; i++)

            if(matrix[i, startJ + currentSize] != 1)

                return;

        for(var j = startJ; j < currentSize; j++)

            if(matrix[startI + currentSize, j] != 1)

                return;

        currentSize++;

        if(maxSize < currentSize)

            maxSize = currentSize;

        GetMaxSubMatrixSizeRecursive(matrix, startI, startJ, currentSize, lengthI, lengthJ, ref maxSize);

    }

}