Maximize the binary matrix by filpping submatrix once | Java program to find maximum number of ones after one flipping in Binary Matrix ; Return number of ones in square submatrix of size k x k starting from ( x , y ) ; Return maximum number of 1 s after flipping a submatrix ; Precomputing the number of 1 s ; Finding the maximum number of 1 s after flipping ; Driver code
class GFG { static final int R = 3 ; static final int C = 3 ; static int cal ( int ones [ ] [ ] , int x , int y , int k ) { return ones [ x + k - 1 ] [ y + k - 1 ] - ones [ x - 1 ] [ y + k - 1 ] - ones [ x + k - 1 ] [ y - 1 ] + ones [ x - 1 ] [ y - 1 ] ; } static int sol ( int mat [ ] [ ] ) { int ans = 0 ; int val = 0 ; int ones [ ] [ ] = new int [ R + 1 ] [ C + 1 ] ; for ( int i = 1 ; i <= R ; i ++ ) for ( int j = 1 ; j <= C ; j ++ ) { if ( mat [ i - 1 ] [ j - 1 ] == 1 ) val = 1 ; ones [ i ] [ j ] = ones [ i - 1 ] [ j ] + ones [ i ] [ j - 1 ] - ones [ i - 1 ] [ j - 1 ] + ( val ) ; } for ( int k = 1 ; k <= Math . min ( R , C ) ; k ++ ) for ( int i = 1 ; i + k - 1 <= R ; i ++ ) for ( int j = 1 ; j + k - 1 <= C ; j ++ ) ans = Math . max ( ans , ( ones [ R ] [ C ] + k * k - 2 * cal ( ones , i , j , k ) ) ) ; return ans ; } static public void main ( String [ ] args ) { int mat [ ] [ ] = { { 0 , 0 , 1 } , { 0 , 0 , 1 } , { 1 , 0 , 1 } } ; System . out . println ( sol ( mat ) ) ; } }