Find Maximum Length Of A Square Submatrix Having Sum Of Elements At | C ++ implementation of the above approach ; Function to return maximum length of square submatrix having sum of elements at - most K ; Matrix to store prefix sum ; Current maximum length ; Variable for storing maximum length of square ; Calculating prefix sum ; Checking whether there exits square with length cur_max + 1 or not ; Returning the maximum length ; Driver code
#include <iostream> NEW_LINE using namespace std ; int maxLengthSquare ( int row , int column , int arr [ ] [ 4 ] , int k ) { int sum [ row + 1 ] [ column + 1 ] ; for ( int i = 1 ; i <= row ; i ++ ) for ( int j = 0 ; j <= column ; j ++ ) sum [ i ] [ j ] = 0 ; int cur_max = 1 ; int max = 0 ; for ( int i = 1 ; i <= row ; i ++ ) { for ( int j = 1 ; j <= column ; j ++ ) { sum [ i ] [ j ] = sum [ i - 1 ] [ j ] + sum [ i ] [ j - 1 ] + arr [ i - 1 ] [ j - 1 ] - sum [ i - 1 ] [ j - 1 ] ; if ( i >= cur_max && j >= cur_max && sum [ i ] [ j ] - sum [ i - cur_max ] [ j ] - sum [ i ] [ j - cur_max ] + sum [ i - cur_max ] [ j - cur_max ] <= k ) { max = cur_max ++ ; } } } return max ; } int main ( ) { int row = 4 , column = 4 ; int matrix [ 4 ] [ 4 ] = { { 1 , 1 , 1 , 1 } , { 1 , 0 , 0 , 0 } , { 1 , 0 , 0 , 0 } , { 1 , 0 , 0 , 0 } } ; int k = 6 ; int ans = maxLengthSquare ( row , column , matrix , k ) ; cout << ans ; return 0 ; }