Задача на поиск субматрицы с наибольшей суммой элементов

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

Существует множество решений этой задачи. Мы начнем с метода грубой силы, а затем займемся оптимизацией.

Метод грубой силы: O(N⁶)

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

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

Это решение потребует O(N⁶) времени, так как необходимо проверить O(N⁴) матриц, а проверка одной матрицы занимает O(N²) времени.

Динамическое программирование: O(N⁴)

Обратите внимание, что предыдущее решение работает медленно из-за расчета суммы элементов матрицы — O(N²) — очень медленная операция. Можно ли сократить это время? Да! Мы можем уменьшить время computeSum до O(1).

Посмотрите на следующий прямоугольник:

scheme

Предположим, что нам известны следующие значения:

Каждое Val* начинается в исходной точке и заканчивается в нижнем правом углу подпрямоугольника. Про эти значения мы знаем следующее:

Или:

Данная информация позволит эффективно рассчитать эти значения для всех точек матрицы:

Можно заранее рассчитать подобные значения и затем найти максимальную субматрицу. Следующий код реализует данный алгоритм.

Оптимизированное решение: O(N³)

Невероятно, но существует еще более оптимальное решение. Если у нас есть R строк и С столбцов, то задачу можно решить за О(R²C) времени.

Вспомните решение задачи про поиск максимального субмассива: для массива целых чисел (integer) найдите субмассив с максимальной суммой. Такой максимальный субмассив можно найти за О(N) времени. Давайте используем это решение для нашей задачи.

Каждую субматрицу можно представить в виде последовательности строк и последовательности столбцов. Можно пройтись по строкам и найти столбцы, дающие максимальную сумму.

Код будет таким:

Теперь остается вопрос: как найти «лучшие» colStart и colEnd?

Рассмотрим субматрицу:

scheme1

Нам необходимо найти colStart и colEnd, которые дают нам максимально возможную сумму всех субматриц rowStart сверху и rowEnd снизу. Можно вычислить сумму каждого столбца и использовать функцию maximumSubArray, которая обсуждалась в начале решения этой задачи.

В предыдущем примере максимальный субмасив охватывал пространство с первой по четвертую колонку. Это означает, что максимальная субматрица должна простираться от (rowStart, первый столбец) до (rowEnd, четвертый столбец).

Теперь мы можем записать следующий псевдокод:

Вычисление суммы в строках 5 и 6 занимает R*C времени (так как требует итерации от rowStart до rowEnd), что дает общее время выполнения О(R ³ C).

В строках 5 и 6 мы добавляли a[0]…a[i] с нуля, даже если на предыдущей итерации внешнего цикла добавились a[0]…a[i-1]. Давайте избавимся от двойной работы.

Полная версия кода выглядит так:

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

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