Maximum sum among all ( a x b ) submatrices for given Q queries | 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 ; Given input ; Function call ; Print answer for all queries
function preProcess ( mat , dp , n , m ) { for ( let i = 0 ; i < m ; i ++ ) { dp [ 0 ] [ i ] = mat [ 0 ] [ i ] ; } for ( let i = 1 ; i < n ; i ++ ) { for ( let j = 0 ; j < m ; j ++ ) { dp [ i ] [ j ] = dp [ i - 1 ] [ j ] + mat [ i ] [ j ] ; } } for ( let i = 0 ; i < n ; i ++ ) { for ( let j = 1 ; j < m ; j ++ ) { dp [ i ] [ j ] += dp [ i ] [ j - 1 ] ; } } } function sumQuery ( dp , tli , tlj , rbi , rbj ) { let 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 ; } function maxSubMatrixSumQueries ( mat , n , m , queries , q ) { let dp = Array ( n ) . fill ( ) . map ( ( ) => Array ( m ) ) ; preProcess ( mat , dp , n , m ) ; let maxSum = new Array ( queries . length ) . fill ( 0 ) ; for ( let qi = 0 ; qi < q ; qi ++ ) { for ( let i = 0 ; i < n - queries [ qi ] [ 0 ] + 1 ; i ++ ) { for ( let j = 0 ; j < m - queries [ qi ] [ 1 ] + 1 ; j ++ ) { maxSum [ qi ] = Math . max ( maxSum [ qi ] , sumQuery ( dp , i , j , i + queries [ qi ] [ 0 ] - 1 , j + queries [ qi ] [ 1 ] - 1 ) ) ; } } } return maxSum ; } let n = 3 , m = 4 ; let mat = [ [ 1 , 2 , 3 , 9 ] , [ 4 , 5 , 6 , 2 ] , [ 8 , 3 , 2 , 6 ] ] ; let Q = 3 ; let Queries = [ [ 1 , 1 ] , [ 2 , 2 ] , [ 3 , 3 ] ] ; let maxSum = maxSubMatrixSumQueries ( mat , n , m , Queries , Q ) ; for ( let i = 0 ; i < Q ; i ++ ) { document . write ( maxSum [ i ] + " " ) ; }