Maximum size sub-matrix with all 1s

using System;

using System.Collections.Generic;

using System.Collections;

using System.Linq;

using System.Text;

 

namespace ConsoleApplication1

{

    class Program

    {

        static void Main(string[] args)

        {

            int[,] matrix = {

                                {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, 1, 1, 1, 0}

                            };

            int startRow = 0, startCol = 0, rowSize = 0, colSize = 0;

            for (int i = 1; i <= matrix.GetLength(0); i++)

            {

                for (int j = 1; j <= matrix.GetLength(1); j++)

                {

                    for (int row = 0; row <= matrix.GetLength(0) – i; row++)

                    {

                        for (int col = 0; col <= matrix.GetLength(1) – j; col++)

                        {

                            if(CheckOne(matrix, row, col, i, j))

                            {

                                if (rowSize == 0)

                                {

                                    rowSize = i;

                                    colSize = j;

                                    startRow = row;

                                    startCol = col;

                                }

                                else

                                {

                                    if((rowSize * colSize) < (i * j))

                                    {

                                        rowSize = i;

                                        colSize = j;

                                        startRow = row;

                                        startCol = col;

                                    }

                                }

                            }

                        }

                    }

                }

            }

            if (rowSize > 0)

            {

                //Printing the maximum size sub matrix with all 1s

                for (int i = startRow; i < (startRow + rowSize); i++)

                {

                    for (int j = startCol; j < (startCol + colSize); j++)

                    {

                        Console.Write(matrix[i, j] + " ");

                    }

                    Console.WriteLine();

                }

            }

        }

        public static bool CheckOne(int[,] matrix, int startRow, int startCol, int rowSize, int colSize)

        {

            bool allOne = true;

            for (int i = startRow; i < (startRow + rowSize); i++)

            {

                for (int j = startCol; j < (startCol + colSize); j++)

                {

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

                    {

                        allOne = false;

                        break;

                    }

                }

                if (allOne == false)

                {

                    break;

                }

            }

            return allOne;

        }

    }

}
 
1 1 1
1 1 1
1 1 1
1 1 1
Press any key to continue . . .
Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s