Maximum sum among all (a x b) submatrices for given Q queries

Given a matrix mat[][] of size N x M and an array queries[] of size Q, containing (a, b) pairs. The task is to find the maximum sum among all (a x b) sub-matrices of the matrix mat[][].  

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

Examples:

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

Naive Approach: The simplest approach to solve this problem is for each query, find sum of every sub-matrix and print the largest one.

Time Complexity: O(Q*(N*M)^2), where Q is the number of queries, N and M are the number of rows and columns of the matrix mat[][].
Auxiliary Space: O(1)

Efficient Approach: This problem can be solved by doing some pre-processing before answering all the queries. Follow the steps below to solve this problem:

• Declare a 2D array, dp where dp[i][j] stores sum of elements from (0, 0) to (i, j).
• Do some preprocessing for input mat[][]. Declare a function say, preProcess(mat, dp, n, m), do the following steps:
  • Iterate in the range [0, m-1] using the variable i and Update dp[0][i] as mat[0][i].
  • Iterate in the range [1, n-1] using the variable i: 
    • Iterate in the range [0, m-1] using the variable j:
      • Update dp[i][j] to dp[i-1][j] + mat[i][j].
  • Iterate in the range [0, n-1] using the variable i: 
    • Iterate in the range [1, m-1] using the variable j:
      • Update dp[i][j] to dp[i][j] + dp[i][j-1].
• Declare an array, maxSum to store answer for each query.
• Declare a function say, sumQuery(dp, tli, tlj, rbi, rbj), where tli and tlj are the row number and column number of top left of query submatrix respectively, rbi and rbj  are the row number and column number of bottom right of query submatrix, that compute sum of submatrix in O(1) time.
  • Initialize a variable res as dp[rbi][rbj] to store sum of the submatrix.
  • If tli is greater 0, then remove elements between (0, 0) and (tli-1, rbj).
  • If tlj is greater than 0, then remove elements between (0, 0) and (rbi, tlj-1).
  • If tli is greater than 0 and tlj is greater than 0, then add dp[tli-1][tlj-1] as elements between (0, 0) and (tli-1, tlj-1) are subtracted twice.
• Iterate in the range [0, q-1] using the variable qi: 
  • Iterate in the range [0, n-queries[qi][0]] using the variable i:
    • Iterate in the range [0, m-queries[qi][1]] using the variable j: 
      • Update maxSum[qi] to max of maxSum[qi] and sumQuery(dp, i, j, i + queries[qi][0] – 1, j + queries[qi][1] – 1)).
• After completing the above steps, print the array maxSum as the answer for each query.

Reference: https://www.geeksforgeeks.org/submatrix-sum-queries/

Below is the implementation of the above approach:

9 20 38 

Time Complexity: O(Q*N*M), where Q is the number of queries, N and M are the number of rows and columns of the matrix mat[][].
Auxiliary Space: O(N*M)