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

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

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

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

Ответы на вопрос(2)

Ваш ответ на вопрос