Весь код будет приведен на C++, а не на чистом C, так как переписать его, если понадобится, не так сложно, но читабельность у плюсов намного выше.
Для начала определим "наивный" алгоритм со сложностью O(n^6):
int main()
{
/*
input: int n, int m, int k, vector<vector<int>> a;
*/
int ans = 0;
int ans_left_x = -1, ans_left_y = -1, ans_right_x = -1, ans_right_y = -1;
for (int x1 = 0; x1 < m; ++x1)
{
for (int y1 = 0; y1 < n; ++y1)
{
for (int x2 = x1; x2 < m; ++x2)
{
for (int y2 = y1; y2 < n; ++y2)
{
// (x1, y1) - верхний левый угол матрицы
// (x2, y2) - нижний правый угол матрицы
int sum = 0;
for (int x = x1; x <= x2; ++x)
{
for (int y = y1; y <= y2; ++y)
sum += a[y][x];
}
int area = (x2 - x1 + 1) * (y2 - y1 + 1);
if (sum <= k && area > ans)
{
ans = area;
ans_left_x = x1;
ans_left_y = y1;
ans_right_x = x2;
ans_right_y = y2;
}
}
}
}
}
/*
output: ans, ans_x1y1x2y2
*/
}
Данный алгоритм совершает примерно
операций.
Теперь стоит заметить одну его интересную оптимизацию:
...
for (int y2 = y1; y2 < n; ++y2)
{
// (x1, y1) - верхний левый угол матрицы
// (x2, y2) - нижний правый угол матрицы
int area = (x2 - x1 + 1) * (y2 - y1 + 1);
if (area < ans)
continue;
...
if (sum <= k)
{
...
}
}
...
Если не считать сумму бесперспективных по площади подматриц, то улучшений площади может произойти не более m*n
(и что-то мне подсказывает, что на самом деле этих улучшений может быть не более m*log(n)
), а следовательно сложность алгоритма резко уменьшается до O(n^2*m^2) + O(n*m) * O(n*m) = O(n^2*m^2)
, что уже синонимично O(n^4)
в данной задаче.
Но все-таки стоит учесть, что это моя недоказанная эвристика, и конкретную оценку сложности можно получить только с помощью обоснованного математического доказательства.
Теперь поговорим о вашей догадке про префиксные суммы (а именно так называется то, о чем вы писали во второй части вопроса). На многомерные пространства префиксные суммы распространяются неохотно, но для двумерного случая формула следующая:
sum(x1, y1, x2, y2) =
pref(x2, y2) -
pref(x1 - 1, y2) -
pref(x2, y1 - 1) +
pref(x1 - 1, y2 - 1)
где pref(x, y) = sum(0, 0, x, y)
Массив префиксных сумм можно вычислить за O(n*m), что можно принять чуть ли не статистической погрешностью. Вычислив массив префиксных сумм, можно доработать прошлое решение следующим образом:
vector<vector<int>> pref(n + 1, vector<int>(m + 1, 0));
for (int i = 0; i < n; i++)
{
int s = 0;
for (int j = 0; j < m; j++)
{
s += a[i][j];
pref[i + 1][j + 1] = pref[i][j + 1] + s;
}
}
...
for (int y2 = y1; y2 < n; ++y2)
{
// (x1, y1) - верхний левый угол матрицы
// (x2, y2) - нижний правый угол матрицы
int area = (x2 - x1 + 1) * (y2 - y1 + 1);
if (area < ans)
continue;
//ко всем индексам была прибавлена единица
//так как pref[i][0] и pref[0][j] содержат нули для удобства вычислений
//и суммы префиксных подматриц (0, 0, x, y) содержатся в pref[y+1][x+1]
int sum =
pref[y2+1][x2+1] -
pref[y2+1][x1] -
pref[y1][x2+1] +
pref[y2][x1];
if (sum <= k)
{
...
}
}
...
Асимптотическая сложность данного решения гарантированно не превосходит O(n^2*m^2)
или O(n^4)
, причем с меньшей константой, чем в решении 2.
Далее стоит подумать об упрощенной задаче: если дана не матрица, а линейный массив.
В таком случае самый длинный отрезок с суммой, не превосходящей K, может быть найден за линейное время с помощью алгоритма "двух указателей". Общую теорию об алгоритме вы можете найти в гугле, если не знакомы.
Идея такова:
Для любых границ отрезков a и b выполняется sum(a, b + 1) > sum(a, b)
и sum(a - 1, b) > sum(a, b)
, так как все элементы больше нуля. Поэтому если отрезок [a, b]
имеет "правильную" сумму, то отрезок [a, b + 1]
либо будет тоже иметь сумму не больше K, либо он включает наибольший подотрезок [x, b + 1]
, сумма которого не больше K, где x > a
. Таким образом для любого конца b мы найдем в процессе работы алгоритма наибольший подотрезок с "правильной" суммой, кончающийся в b.
Теперь применим данное решение в двумерном варианте задачи. Мы можем "сжать" любую подматрицу по столбцам, сложив элементы, после чего она превратится в одномерный массив, для которого мы уже умеем решать задачу.
Пример:
3 1 4 1
5 9 2 6 ---> 13 13 11 16
5 3 5 9
Тогда переберем возможные y1 и y2 для подматриц и решим задачу за O(n^2*m)
.
//Новые префиксные суммы - линейные префиксные по столбцам
vector<vector<int>> pref(m, vector<int>(n + 1, 0));
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
pref[i][j + 1] = pref[i][j] + a[i][j];
}
for (int y1 = 0; y1 < n; ++y1)
{
for (int y2 = y1; y2 < n; ++y2)
{
//Неявно сожмем подматрицу (0, y1) (m - 1, y2) до одномерной, сложив значения по столбцам
//Тогда решим задачу для линейного массива с помощью "двух указателей"
int x1 = 0;
int s = 0;
for (int x2 = 0; x2 < m; ++x2)
{
s += pref[x2][y2 + 1] - pref[x2][y1];
while (s > k)
{
s -= pref[x1][y2 + 1] - pref[x1][y1];
x1++;
}
int area = (y2 - y1 + 1) * (x2 - x1 + 1);
if (area > ans)
{
//...
}
}
}
}
Стоит отметить, что тут n и m входят в разных степенях в оценку сложности, поэтому стоит перебирать y1 и y2 или x1 и x2 в зависимости от того, какая сторона меньше.
Я не буду утверждать точно, но с большой долей вероятности положительность элементов дает возможность использовать тернарный и бинарный поиск следующим образом:
- for x in 0 .. m - 1 - перебор правой границы
- for y in 0 .. n - 1 - перебор нижней границы
- ternar(0, y) - поиск оптимальной верхней границы
- binar(0, x) - поиск минимальной левой границы, для которой сумма правильна
- sum(x1, y1, x2, y2) - через префиксные суммы
(цифрами обозначена степень вложенности)
Также я не отрицаю, что если алгоритм выше корректен, то его можно как-то улучшить, убрав квадрат у логарифма в асимтотической сложности, например используя решения для одномерного массива.
И если вы ироничный студент, и у вас ироничный преподаватель, то рекомендую вам использовать алгоритм со сложностью O(n^5), использующий линейные префиксные суммы.
Если вы сумеете написать адекватный (то есть не высосанный из пальца) алгоритм O(n^5 log(n)) или алгоритм O(n*m), то напишите его, пожалуйста, отдельным ответом и вызовите меня через @ в комментариях к моему ответу. Также я был бы рад, если бы кто-то провел бенчмарк приведенных решений и проверил их на корректность.
O(n**2)
. Самый наивный подход перебирает все возможные дочерние матрицы(i, j, nrows, ncolumns)
--O(n**4)
и вычисляет наивно сумму с самого начала n*m --O(n**2)
->O(n**6)
алгоритм. Если использовать S[i,j] матрицу, то можно за O(1) сумму вычислять:Sum(i,j,nrows,ncolumns) = S[i+nrows,j+ncolumns] - S[i+nrows,j] - S[i,j+ncolumns] +S[i,j]
то есть используя S[i,j] наивный алгоритм становитсяO(n**4)
по времени иO(n**2)
в памяти. Это достаточно для вашего вопроса?