4
Предположим, у вас есть матрица N × N, где каждая строка имеет ровно один ненулевой элемент, и каждый столбец имеет ровно один ненулевой элемент (ненулевой элемент элементы могут быть как положительными, так и отрицательными). Мы хотим найти подматрицу максимальной суммы. Насколько эффективно мы можем это сделать?Максимальная сумма матрицы подматрицы NxN и с N-ненулевыми значениями, только O (N^2)
Матрица имеет размерность N × N и только N отличных от нуля элементов. N настолько велик, что я не могу использовать алгоритм O (N). Кто-нибудь знает, как решить это вовремя O (N), O (N log N) или какая-то еще сложная временная сложность?
Спасибо!
Что такое «тривиальная ситуация»? – Matt
Я предполагаю, что местоположение N ненулевых элементов неизвестно (а не разреженная матрица), а значения являются как положительными, так и отрицательными? – IdeaHat
Если вы не используете разреженную матрицу, то O (N^2) - это лучшее, что вы можете сделать, так как вам, по крайней мере, нужно читать каждый элемент. Вероятно, существует некоторое обобщение алгоритма Кадане на два измерения. http://stackoverflow.com/questions/12339280/find-max-sum-of-elements-in-array – Adam