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