Лабораторный практикум по информатике

Найти прямоугольник наибольшей площади, заполненный единицами.

Площадь прямоугольников изменяется от максимальной (весь мас- сив) до минимальной (прямоугольник, состоящий из одной 1). Каждый прямоугольник конкретной площади может быть построен множеством способов. Для площади S допустимый прямоугольник – это такой, про- изведение сторон которого равно S. Мы должны для каждого значения площади перебрать все допустимые способы построения прямоугольни- ков. Каждый прямоугольник конкретной площади и формы может рас- полагаться в массиве различным образом. Точнее сказать, его левая верхняя вершина может находиться в разных точках массива. Следова- тельно, для прямоугольника определенной площади и формы мы долж- ны перебрать все возможные расположения.

Может показаться, что программа для большого массива будет ра- ботать слишком долго, но есть серьезные возможности для ее ускоре- ния. А именно:

1. 
   Если площадь перебирать от максимальной к минимальной, то пер- вый найденный прямоугольник и будет искомым.
   
2. 
   Прямоугольник конкретной площади и формы не поместится в лю- бом положении в массив.