В книге Bentley Programming Pearls (2-е изд.) в главе о задаче максимального подмассива описывается ее двумерная версия:
...нам дан массив n × n вещественных чисел, и мы должны найти максимальную сумму, содержащуюся в любом прямоугольном подмассиве. В чем сложность этой проблемы?
Бентли упоминает, что на дату публикации книги (2000 г.) проблема поиска оптимального решения была открытой.
Так ли это и сейчас? Какое самое известное решение? Любой указатель на недавнюю литературу?
1D-решение этой проблемы (максимальный подмассив) — это Theta(n) с использованием алгоритма под названием «Алгоритм Кадане» (я уверен, что есть и другие алгоритмы, но у меня есть личный опыт работы с этим). Известно, что 2D-решение этой проблемы (максимальный подпрямоугольник) равно O(n^3) с использованием реализации алгоритма Кадане (опять же, я уверен, что есть и другие, но я использовал это раньше).
Хотя мы знаем, что двумерное решение можно найти в Theta(n^3), никто не смог доказать, является ли n^3 нижней границей. Для многих алгоритмов, когда вы увеличиваете размерность, вы увеличиваете нижнюю границу алгоритма на постоянную величину. В этой конкретной проблеме сложность не увеличивается линейно, и поэтому нет известного решения, работающего для любого заданного измерения, поэтому проблема все еще остается открытой.
В отношении аналогичного случая: мы знаем, что 2 матрицы можно перемножить за время n^3. Есть также алгоритм, который может сделать это за n ^ 2,8, я думаю. Однако нет математики, указывающей на то, что мы не можем получить его ниже n ^ 2,8, поэтому это все еще «открытый» алгоритм.
2.374 en.wikipedia.org/wiki/Coppersmith %E2%80%93алгоритм Винограда . Однако они непрактичны из-за больших коэффициентов.
- person WestCoastProjects; 04.01.2018
К вашему сведению, в новом издании книги есть ответ, но он настолько расплывчатый, что я не знаю, что он повлечет за собой.
В любом случае, я бы использовал разделяй и властвуй + динамическое программирование, чтобы решить эту проблему. Давайте определим MaxSum(x, y) как максимальную сумму любого подмассива внутри прямоугольника, ограниченного самым верхним левым углом массива N X N, с высотой y и шириной x. (поэтому ответ на вопрос будет в MaxSum(n-1, n-1))
MaxSum(x, y) is the max between:
1) MaxSum(x, y-1)
2) MaxSum(x-1, y)
3) Array[x, y] (the number in this N X N array for this specific location)
4) MaxEnding(x, y-1) + SUM of all elements from Array[MaxEndingXStart(x, y-1), y] to Array[x, y]
5) MaxEnding(x-1, y) + SUM of all elements from Array[x, MaxEndingYStart(x-1, y)] to Array[x, y]
MaxEnding(x, y-1) – это максимальная сумма любого подмассива, ВКЛЮЧАЮЩЕГО символ # в Array[x, y-1]. Аналогично, MaxEnding(x-1, y) — это максимальная сумма любого подмассива, ВКЛЮЧАЮЩЕГО # в Array[x-1, y]. MaxEndingXStart(x, y-1) — это НАЧАЛЬНАЯ координата x подмассива, который имеет максимальную сумму любого подмассива, ВКЛЮЧАЮЩЕГО # в Array[x, y-1]. MaxEndingYStart (x-1, y) — это НАЧАЛЬНАЯ координата y подмассива, который имеет максимальную сумму любого подмассива, ВКЛЮЧАЮЩЕГО # в Array[x-1, y].
2 суммы в #4 и #5 ниже можно легко вычислить, сохраняя сумму всех элементов, встречающихся в определенной строке, по мере прохождения каждого столбца, а затем вычитая 2 суммы, чтобы получить сумму для определенного раздела.
Чтобы реализовать это, вам нужно будет использовать восходящий подход, поскольку вам нужно вычислить Max(x, y-1), Max(x-1, y), MaxEnding(x, y-1) и MaxEnding( x-1, y).. так что вы можете выполнять поиск при вычислении MaxEnding (x, y).
//first do some preprocessing and store Max(0, i) for all i from 0 to n-1.
//and store Max(i, 0) for all i from 0 to n-1.
for(int i =1; i < n; i++){
for(int j=1; j < n; j++) {
//LOGIC HERE
}
}
