Maximums of all 2D subarrays of size A x B

Question

Let's say I have a 2D array of size N x M. I want to print out the sum of the maximum of every subarray of size A x B.

For example, let's say for this 3 x 3 array, A = 2 and B = 2.

Input:
1 2 3
4 5 6
7 8 9

the output should be:

Output:
from (0, 0) to (1, 1): 5
from (0, 1) to (1, 2): 6
from (1, 0) to (2, 1): 8
from (1, 1) to (2, 2): 9

Answer: 5 + 6 + 8 + 9 = 28

I've tried using a 2D Sparse Table, but it's definitely not fast enough. I'm trying to achieve O(N * M), if that's possible.

Answer 1

This answer describes a way of extending the 1-D (array) algorithm for finding the maximum over a sliding window (please read Method 3, the one that uses a deque). Essentially:

1. Find the maximum of every horizontal sequence of B elements, effectively reducing the matrix to N - B + 1 columns.
2. Find the maximum of every vertical sequence of A elements, effectively reducing the matrix to M - A + 1 rows.
3. The remaining elements are your window maxima, simply add them up.