0
Мне дана задача написать алгоритм для вычисления максимального двухмерного подмножества матрицы целых чисел. - Однако я не заинтересован в помощи для такого алгоритма, я больше заинтересован в понимании сложности для лучшего худшего случая, который может решить это.Максимальное двумерное подмножество
Наш текущий алгоритм подобен O (n^3).
Я рассматривал, что-то подобное делит и побеждает, разбивая матрицу на ряд подматриц, просто добавляя элементы внутри матриц; и тем самым ограничивая число матриц, которые нужно рассмотреть, чтобы найти приближенное решение.
Это будет сама матрица, не так ли? ;) – John
Что? - Не уверен, что я получу то, что вы сказали, действительно ли это не зависело бы от количества отрицательных чисел в матрице? – Skeen
Ahh хорошая точка. Вы сказали, что целые числа не являются неотрицательными целыми числами. ;) Итак, вы ищете суб-прямоугольник чисел внутри вашей матрицы, чтобы сумма чисел в этом прямоугольнике была максимальной, чем сумма всех возможных прямоугольников? – John