using System;

public class Program {

    public static void Main() {

        var matrices = new []{

            new [] {

                "00000",

                "00000",

                "00000",

                "00000",

                "00000"

            },

            new [] {

                "10000",

                "00000",

                "10000",

                "10000",

                "00000"

            },

            new [] {

                "11011",

                "01101",

                "11110",

                "11111",

                "01111"

            },

            new [] {

                "101101",

                "111111",

                "011111",

                "111111",

                "001111",

                "011111"

            }

        };

​

        foreach(var matrix in matrices) {

            int maxArea = CalculateMaxRectangleArea(matrix);

            Console.WriteLine($"The max rectangle area is {maxArea}");

        }

    }

    static int CalculateMaxRectangleArea(string[] matrix) {

        int maxArea = 0, loopCounter = 0;

        for (int i = 0; i < matrix.Length; i++) {

            for (int j = 0; j < matrix[i].Length; j++) {

                int maxVerticalExtend = matrix.Length - i;

                for (int horizontalExtend = 0; j + horizontalExtend < matrix[i].Length; horizontalExtend++) {

                    int verticalExtend = 0;

                    for (; verticalExtend < maxVerticalExtend; verticalExtend++) {

                        loopCounter++;

                        if (matrix[i + verticalExtend][j + horizontalExtend] == '0') // Not every cell is 1, we break out prematurely

                            break;

                        int area = (horizontalExtend + 1) * (verticalExtend + 1);

                        if (area > maxArea)

                            maxArea = area;

                    }

                    maxVerticalExtend = verticalExtend;

                }

            }

        }

        Console.WriteLine($"The loop count is {loopCounter}");

        return maxArea;

    }

}