Maximum size of square such that all submatrices of that size have sum less than K | C # implementation to find the maximum size square submatrix such that their sum is less than K ; Size of matrix ; Function to preprocess the matrix for computing the sum of every possible matrix of the given size ; Loop to copy the first row of the matrix into the aux matrix ; Computing the sum column - wise ; Computing row wise sum ; Function to find the sum of a submatrix with the given indices ; Overall sum from the top to right corner of matrix ; Removing the sum from the top corer of the matrix ; Remove the overlapping sum ; Add the sum of top corner which is subtracted twice ; Function to find the maximum square size possible with the such that every submatrix have sum less than the given sum ; Loop to choose the size of matrix ; Loop to find the sum of the matrix of every possible submatrix ; Driver Code
using System ; public class GFG { static readonly int N = 4 ; static readonly int M = 5 ; static void preProcess ( int [ , ] mat , int [ , ] aux ) { for ( int i = 0 ; i < M ; i ++ ) aux [ 0 , i ] = mat [ 0 , i ] ; for ( int i = 1 ; i < N ; i ++ ) for ( int j = 0 ; j < M ; j ++ ) aux [ i , j ] = mat [ i , j ] + aux [ i - 1 , j ] ; for ( int i = 0 ; i < N ; i ++ ) for ( int j = 1 ; j < M ; j ++ ) aux [ i , j ] += aux [ i , j - 1 ] ; } static int sumQuery ( int [ , ] aux , int tli , int tlj , int rbi , int rbj ) { int res = aux [ rbi , rbj ] ; if ( tli > 0 ) res = res - aux [ tli - 1 , rbj ] ; if ( tlj > 0 ) res = res - aux [ rbi , tlj - 1 ] ; if ( tli > 0 && tlj > 0 ) res = res + aux [ tli - 1 , tlj - 1 ] ; return res ; } static int maximumSquareSize ( int [ , ] mat , int K ) { int [ , ] aux = new int [ N , M ] ; preProcess ( mat , aux ) ; for ( int i = Math . Min ( N , M ) ; i >= 1 ; i -- ) { bool satisfies = true ; for ( int x = 0 ; x < N ; x ++ ) { for ( int y = 0 ; y < M ; y ++ ) { if ( x + i - 1 <= N - 1 && y + i - 1 <= M - 1 ) { if ( sumQuery ( aux , x , y , x + i - 1 , y + i - 1 ) > K ) satisfies = false ; } } } if ( satisfies == true ) return ( i ) ; } return 0 ; } public static void Main ( String [ ] args ) { int K = 30 ; int [ , ] mat = { { 1 , 2 , 3 , 4 , 6 } , { 5 , 3 , 8 , 1 , 2 } , { 4 , 6 , 7 , 5 , 5 } , { 2 , 4 , 8 , 9 , 4 } } ; Console . Write ( maximumSquareSize ( mat , K ) ) ; } }