Максимальная сумма среди всех (axb) подматриц для заданных Q запросов

Опубликовано: 22 Сентября, 2022

Дана матрица mat[][] размера N x M и массив запросов[] размера Q, содержащий пары (a, b) . Задача состоит в том, чтобы найти максимальную сумму среди всех (axb) подматриц матрицы mat[][] .

Note: The rows and columns of the sub-matrix must be contiguous.

Примеры:

Input: N = 3, M = 4, Q = 1, queries[] = {(3, 2)}
mat[][] = {{1, 2, 3, 9},
{4, 5, 6, 2},
{8, 3, 2, 6}}

Output: 28
Explanation:
Here a = 3 and b = 2
The first 3×2 submatrix is:
1 2
4 5
8 3
The sum of elements in this is 23.
The second 3×2 submatrix is:
2 3
5 6
3 2
The sum of elements in this is 21.
The third 3×2 submatrix is:
3 9
6 2
2 6
The sum of elements in this is 28.
The maximum among these are 28.
Input: N = 3, M = 4, Q = 3, queries[] = {(1, 1), (2, 2), (3, 3)}
mat[][] = {{1, 2, 3, 9},
{4, 5, 6, 2},
{8, 3, 2, 6}}

Output: 9 20 38

Наивный подход: самый простой подход к решению этой проблемы — для каждого запроса найти сумму каждой подматрицы и вывести наибольшую из них.

Временная сложность: O(Q*(N*M)^2), где Q — количество запросов, N и M — количество строк и столбцов матрицы mat[][].
Вспомогательное пространство: O(1)

Эффективный подход: эту проблему можно решить, выполнив некоторую предварительную обработку, прежде чем отвечать на все запросы. Выполните следующие шаги, чтобы решить эту проблему:

Объявите двумерный массив dp , где dp[i][j] хранит сумму элементов от (0, 0) до (i, j).
Сделайте некоторую предварительную обработку для ввода mat[][]. Объявите функцию, скажем, preProcess(mat, dp, n, m), выполните следующие шаги:
- Итерация в диапазоне [0, m-1], используя переменную i и Обновите dp[0][i] как mat[0][i].
- Выполните итерацию в диапазоне [1, n-1], используя переменную i :
  - Выполните итерацию в диапазоне [0, m-1], используя переменную j:
    - Обновите dp[i][j] до dp[i-1][j] + mat[i][j].
- Итерация в диапазоне [0, n-1] с использованием переменной i :
  - Выполните итерацию в диапазоне [1, m-1], используя переменную j:
    - Обновите dp[i][j] до dp[i][j] + dp[i][j-1].
Объявите массив maxSum для хранения ответов на каждый запрос.
Объявите функцию, скажем, sumQuery(dp, tli, tlj, rbi, rbj), где tli и tlj — номер строки и номер столбца в левом верхнем углу подматрицы запроса соответственно, rbi и rbj — номер строки и номер столбца в правом нижнем углу. подматрицы запроса, которые вычисляют сумму подматрицы за время O(1) .
- Инициализируйте переменную res как dp[rbi][rbj] для хранения суммы подматрицы.
- Если tl i больше 0 , то удалите элементы между (0, 0) и (tli-1, rbj) .
- Если tlj больше 0, то удалите элементы между (0, 0) и (rbi, tlj-1).
- Если tli больше 0 и tlj больше 0, то добавьте dp[tli-1][tlj-1] , так как элементы между (0, 0) и (tli-1, tlj-1) вычитаются дважды.
Выполните итерацию в диапазоне [0, q-1], используя переменную qi :
- Выполните итерацию в диапазоне [0, n-запросов[qi][0]] , используя переменную i:
  - Выполните итерацию в диапазоне [0, m-queries[qi][1]] с использованием переменной j :
    - Обновите maxSum[qi] до max maxSum[qi] и sumQuery(dp, i, j, i + query[qi][0] – 1, j + query[qi][1] – 1)).
После выполнения вышеуказанных шагов выведите массив maxSum в качестве ответа на каждый запрос.

Ссылка: https://www.geeksforgeeks.org/submatrix-sum-queries/

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(Q*N*M), где Q — количество запросов, N и M — количество строк и столбцов матрицы mat[][].
Вспомогательное пространство: O(N*M)

Максимальная сумма среди всех (axb) подматриц для заданных Q запросов

РЕКОМЕНДУЕМЫЕ СТАТЬИ