Представьте, что существует квадратная матрица, каждый пиксел которой может быть черным или белым. Разработайте алгоритм поиска максимального субквадрата, у которого все стороны черные

Эту задачу также можно решить двумя способами: простым и сложным. Давайте рассмотрим оба решения.

«Простое» решение: O(N4)

Мы знаем, что длина стороны самого большого квадрата равна N и существует только один квадрат размером N*N. Можно проверить, является ли квадрат искомым, и сообщить, если это так.

Если квадрат размером N*N не найден, можно попытаться найти следующий квадрат: (N-1)*(N-1). Проверяя все квадраты этого размера, мы возвращаем первый найденный квадрат. Затем аналогичные операции повторяются для N-2, N-3 и т. д. Так как каждый раз мы уменьшаем размер квадрата, то первый найденный квадрат будет самым большим.

Наш код работает так:

Решение с предварительной обработкой: O(N3)

Неторопливость «простого» решения связана с тем, что мы должны произвести O(N) операций при каждой проверке квадрата–кандидата. Проведя предварительную обработку, можно сократить время isSquare до O(1), тогда алгоритм потребует O(N3) времени.

isSquare пытается узнать, не являются ли нулевыми squareSize, находящиеся правее (и ниже) определенных ячеек. А эту информацию можно узнать заранее.

Мы выполним проверку справа налево и снизу вверх. Для каждой ячейки нужно рассчитать:

Посмотрите на значения для некоторой матрицы.

table
Теперь, вместо того чтобы итерировать по O(N) элементов, метод isSquare проверяет углы на zerosRight и zerosBelow.

Далее приведен код этого алгоритма. Обратите внимание, что findSquare и findSquare — WithSize совпадают, за исключением вызова processMatrix и последующей работы с новым типом данных:

Разбор задачи по книге «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию»