Largest rectangular sub | C ++ implementation to find largest rectangular sub - matrix having sum divisible by k ; static readonly int SIZE = 10 ; ; function to find the longest subarray with sum divisible by k . The function stores starting and ending indexes of the subarray at addresses pointed by start and finish pointers respectively . ; unordered map ' um ' implemented as hash table ; ' mod _ arr [ i ] ' stores ( sum [ 0. . i ] % k ) ; traverse arr [ ] and build up the array ' mod _ arr [ ] ' ; as the sum can be negative , taking modulo twice ; if true then sum ( 0. . i ) is divisible by k ; update variables ; if value ' mod _ arr [ i ] ' not present in ' um ' then store it in ' um ' with index of its first occurrence ; if true , then update variables ; function to find largest rectangular sub - matrix having sum divisible by k ; Variables to store the final output ; Set the left column ; Initialize all elements of temp as 0 ; Set the right column for the left column set by outer loop ; Calculate sum between current left and right for every row ' i ' ; The longSubarrWthSumDivByK ( ) function sets the values of ' start ' and ' finish ' . So submatrix having sum divisible by ' k ' between ( start , left ) and ( finish , right ) which is the largest submatrix with boundary columns strictly as left and right . ; Calculate current area and compare it with maximum area so far . If maxArea is less , then update maxArea and other output values ; Print final values ; Driver program to test above functions
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define SIZE  10 NEW_LINE #define SIZE  10 NEW_LINE void longSubarrWthSumDivByK ( int arr [ ] , int n , int k , int & start , int & finish ) { unordered_map < int , int > um ; int mod_arr [ n ] ; int curr_sum = 0 , max = 0 ; for ( int i = 0 ; i < n ; i ++ ) { curr_sum += arr [ i ] ; mod_arr [ i ] = ( ( curr_sum % k ) + k ) % k ; } for ( int i = 0 ; i < n ; i ++ ) { if ( mod_arr [ i ] == 0 ) { max = i + 1 ; start = 0 ; finish = i ; } else if ( um . find ( mod_arr [ i ] ) == um . end ( ) ) um [ mod_arr [ i ] ] = i ; else if ( max < ( i - um [ mod_arr [ i ] ] ) ) { max = i - um [ mod_arr [ i ] ] ; start = um [ mod_arr [ i ] ] + 1 ; finish = i ; } } } void findLargestSubmatrix ( int mat [ SIZE ] [ SIZE ] , int n , int k ) { int finalLeft , finalRight , finalTop , finalBottom ; int left , right , i , maxArea = 0 ; int temp [ n ] , start , finish ; for ( left = 0 ; left < n ; left ++ ) { memset ( temp , 0 , sizeof ( temp ) ) ; for ( right = left ; right < n ; right ++ ) { for ( i = 0 ; i < n ; ++ i ) temp [ i ] += mat [ i ] [ right ] ; longSubarrWthSumDivByK ( temp , n , k , start , finish ) ; if ( maxArea < ( ( right - left + 1 ) * ( finish - start + 1 ) ) ) { finalLeft = left ; finalRight = right ; finalTop = start ; finalBottom = finish ; maxArea = ( right - left + 1 ) * ( finish - start + 1 ) ; } } } cout << " ( Top , ▁ Left ) : ▁ ( " << finalTop << " , ▁ " << finalLeft << " ) STRNEWLINE " ; cout << " ( Bottom , ▁ Right ) : ▁ ( " << finalBottom << " , ▁ " << finalRight << " ) STRNEWLINE " ; cout << " Area : ▁ " << maxArea ; } int main ( ) { int mat [ SIZE ] [ SIZE ] = { { 1 , 2 , -1 , -4 } , { -8 , -3 , 4 , 2 } , { 3 , 8 , 10 , 1 } , { -4 , -1 , 1 , 7 } } ; int n = 4 , k = 5 ; findLargestSubmatrix ( mat , n , k ) ; return 0 ; }