Нахождение подматрицы с максимально возможной суммой в O (n ^ 2)

Question

Я пытаюсь написать программу на Java, которая при задании матрицы MxN найдет (непрерывную) подматрицу с наибольшей суммой чисел. Затем программа должна вернуть координаты верхнего левого угла подматрицы и координаты нижнего правого угла. Матрица может содержать отрицательные числа, и матрица, и подматрица не обязательно должны быть квадратными.

Я видел, что это обсуждалось здесь: Получение подматрицы с максимальной суммой? и решение там, кажется, O (n ^ 3) Мой друг сказал, что им когда-то удалось решить эту проблему в O (n ^ 2). Также предлагается здесь. Возможно ли это?

Есть ли какой-нибудь доступный код, который решает эту проблему наиболее эффективным способом?

Answer 1

Вы (скорее всего) не можете решить вашу проблему в O(n^2), по крайней мере, такой алгоритм не известен.Оптимальное решение имеет субкубическую сложность, но его очень сложно реализовать и, вероятно, медленнее на практике.Вы можете прочитать статью об этом здесь .

Обычный используемый алгоритм - это O(n^3), указанный в найденном вами вопросе.

Answer 2

(S) Он твой друг ... так что просто спроси его / ее, и поделись с нами тоже:)