Максимальная двумерная подмножество-сумма

Question

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

Наш текущий алгоритм подобен O ​​(n ^3).

Я размышлял о чем-то похожем: разделяй и властвуй, разбивая матрицу на несколько подматриц, просто складывая элементы внутри матриц;и тем самым ограничив число матриц, которые необходимо учитывать, чтобы найти приближенное решение.

Answer 1

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

Answer 2

Худший случай (исчерпывающий поиск) определенно не хуже , чем O (n ^ 3). Есть несколько описаний этого в Интернете.

Лучший вариант может быть намного лучше: O (1). Если все элементы неотрицательны, то ответом является сама матрица. Если элементы не положительны, ответом является элемент, значение которого ближе всего к нулю.

Аналогично, если на краях вашей матрицы есть целые строки / столбцы, которые являются не чем иным, как неположительными целыми числами, вы можете отрубить их в своем поиске.