Maximum sum among all ( a x b ) submatrices for given Q queries | C ++ program for the above approach ; Function to preprcess input mat [ N ] [ M ] . This function mainly fills dp [ N ] [ M ] such that dp [ i ] [ j ] stores sum of elements from ( 0 , 0 ) to ( i , j ) ; Copy first row of mat [ ] [ ] to dp [ ] [ ] ; Do column wise sum ; Do row wise sum ; A O ( 1 ) time function to compute sum of submatrix between ( tli , tlj ) and ( rbi , rbj ) using dp [ ] [ ] which is built by the preprocess function ; Result is now sum of elements between ( 0 , 0 ) and ( rbi , rbj ) ; Remove elements between ( 0 , 0 ) and ( tli - 1 , rbj ) ; Remove elements between ( 0 , 0 ) and ( rbi , tlj - 1 ) ; Add dp [ tli - 1 ] [ tlj - 1 ] as elements between ( 0 , 0 ) and ( tli - 1 , tlj - 1 ) are subtracted twice ; Function to find the maximum sum among all ( a x b ) sub - matrices of the matrix ; Function call ; Run a loop for finding answer for all queries ; Driver Code ; Given input ; Function call ; Print answer for all queries
#include <bits/stdc++.h> NEW_LINE using namespace std ; void preProcess ( vector < vector < int > > & mat , vector < vector < int > > & dp , int n , int m ) { for ( int i = 0 ; i < m ; i ++ ) { dp [ 0 ] [ i ] = mat [ 0 ] [ i ] ; } for ( int i = 1 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { dp [ i ] [ j ] = dp [ i - 1 ] [ j ] + mat [ i ] [ j ] ; } } for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 1 ; j < m ; j ++ ) { dp [ i ] [ j ] += dp [ i ] [ j - 1 ] ; } } } int sumQuery ( vector < vector < int > > dp , int tli , int tlj , int rbi , int rbj ) { int res = dp [ rbi ] [ rbj ] ; if ( tli > 0 ) res = res - dp [ tli - 1 ] [ rbj ] ; if ( tlj > 0 ) res = res - dp [ rbi ] [ tlj - 1 ] ; if ( tli > 0 && tlj > 0 ) res = res + dp [ tli - 1 ] [ tlj - 1 ] ; return res ; } vector < int > maxSubMatrixSumQueries ( vector < vector < int > > mat , int n , int m , vector < vector < int > > queries , int q ) { vector < vector < int > > dp ( n , vector < int > ( m ) ) ; preProcess ( mat , dp , n , m ) ; vector < int > maxSum ( ( int ) queries . size ( ) ) ; for ( int qi = 0 ; qi < q ; qi ++ ) { for ( int i = 0 ; i < n - queries [ qi ] [ 0 ] + 1 ; i ++ ) { for ( int j = 0 ; j < m - queries [ qi ] [ 1 ] + 1 ; j ++ ) { maxSum [ qi ] = max ( maxSum [ qi ] , sumQuery ( dp , i , j , i + queries [ qi ] [ 0 ] - 1 , j + queries [ qi ] [ 1 ] - 1 ) ) ; } } } return maxSum ; } int main ( ) { int n = 3 , m = 4 ; vector < vector < int > > mat = { { 1 , 2 , 3 , 9 } , { 4 , 5 , 6 , 2 } , { 8 , 3 , 2 , 6 } } ; int Q = 3 ; vector < vector < int > > Queries = { { 1 , 1 } , { 2 , 2 } , { 3 , 3 } } ; vector < int > maxSum = maxSubMatrixSumQueries ( mat , n , m , Queries , Q ) ; for ( int i = 0 ; i < Q ; i ++ ) { cout << maxSum [ i ] << " ▁ " ; } }