Найти максимальную площадь матрицы с суммой элементов меньше или равной k

Весь код будет приведен на 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 в зависимости от того, какая сторона меньше.

---

Я не буду утверждать точно, но с большой долей вероятности положительность элементов дает возможность использовать тернарный и бинарный поиск следующим образом:

1. for x in 0 .. m - 1 - перебор правой границы
2. for y in 0 .. n - 1 - перебор нижней границы
3. ternar(0, y) - поиск оптимальной верхней границы
4. binar(0, x) - поиск минимальной левой границы, для которой сумма правильна
5. sum(x1, y1, x2, y2) - через префиксные суммы

(цифрами обозначена степень вложенности)

---

Также я не отрицаю, что если алгоритм выше корректен, то его можно как-то улучшить, убрав квадрат у логарифма в асимтотической сложности, например используя решения для одномерного массива.

---

И если вы ироничный студент, и у вас ироничный преподаватель, то рекомендую вам использовать алгоритм со сложностью O(n^5), использующий линейные префиксные суммы.

---

Если вы сумеете написать адекватный (то есть не высосанный из пальца) алгоритм O(n^5 log(n)) или алгоритм O(n*m), то напишите его, пожалуйста, отдельным ответом и вызовите меня через @ в комментариях к моему ответу. Также я был бы рад, если бы кто-то провел бенчмарк приведенных решений и проверил их на корректность.