Maximum size square Sub | C # program for the above approach ; Function to find the maximum size of matrix with sum <= K ; N size of rows and M size of cols ; To store the prefix sum of matrix ; Create prefix sum ; Traverse each rows ; Update the prefix sum till index i x j ; To store the maximum size of matrix with sum <= K ; Traverse the sum matrix ; Index out of bound ; Maximum possible size of matrix ; Binary Search ; Find middle index ; Check whether sum <= K or not If Yes check for other half of the search ; Else check it in first half ; Update the maximum size matrix ; Print the readonly answer ; Driver Code ; Given target sum ; Function Call
using System ; class GFG { static void findMaxMatrixSize ( int [ , ] arr , int K ) { int i , j ; int n = arr . GetLength ( 0 ) ; int m = arr . GetLength ( 1 ) ; int [ , ] sum = new int [ n + 1 , m + 1 ] ; for ( i = 0 ; i <= n ; i ++ ) { for ( j = 0 ; j <= m ; j ++ ) { if ( i == 0 j == 0 ) { sum [ i , j ] = 0 ; continue ; } sum [ i , j ] = arr [ i - 1 , j - 1 ] + sum [ i - 1 , j ] + sum [ i , j - 1 ] - sum [ i - 1 , j - 1 ] ; } } int ans = 0 ; for ( i = 1 ; i <= n ; i ++ ) { for ( j = 1 ; j <= m ; j ++ ) { if ( i + ans - 1 > n j + ans - 1 > m ) break ; int mid , lo = ans ; int hi = Math . Min ( n - i + 1 , m - j + 1 ) ; while ( lo < hi ) { mid = ( hi + lo + 1 ) / 2 ; if ( sum [ i + mid - 1 , j + mid - 1 ] + sum [ i - 1 , j - 1 ] - sum [ i + mid - 1 , j - 1 ] - sum [ i - 1 , j + mid - 1 ] <= K ) { lo = mid ; } else { hi = mid - 1 ; } } ans = Math . Max ( ans , lo ) ; } } Console . Write ( ans + " STRNEWLINE " ) ; } public static void Main ( String [ ] args ) { int [ , ] arr = { { 1 , 1 , 3 , 2 , 4 , 3 , 2 } , { 1 , 1 , 3 , 2 , 4 , 3 , 2 } , { 1 , 1 , 3 , 2 , 4 , 3 , 2 } } ; int K = 4 ; findMaxMatrixSize ( arr , K ) ; } }