Maximize the binary matrix by filpping submatrix once | PHP 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
< ? php $ R = 3 ; $ C = 3 ; function cal ( $ ones , $ x , $ y , $ 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 ] ; } function sol ( $ mat ) { global $ C , $ R ; $ ans = 0 ; $ ones = array_fill ( 0 , $ R + 1 , array_fill ( 0 , $ C + 1 , 0 ) ) ; for ( $ i = 1 ; $ i <= $ R ; $ i ++ ) for ( $ j = 1 ; $ j <= $ C ; $ j ++ ) $ ones [ $ i ] [ $ j ] = $ ones [ $ i - 1 ] [ $ j ] + $ ones [ $ i ] [ $ j - 1 ] - $ ones [ $ i - 1 ] [ $ j - 1 ] + ( int ) ( $ mat [ $ i - 1 ] [ $ j - 1 ] == 1 ) ; for ( $ k = 1 ; $ k <= min ( $ R , $ C ) ; $ k ++ ) for ( $ i = 1 ; $ i + $ k - 1 <= $ R ; $ i ++ ) for ( $ j = 1 ; $ j + $ k - 1 <= $ C ; $ j ++ ) $ ans = max ( $ ans , ( $ ones [ $ R ] [ $ C ] + $ k * $ k - 2 * cal ( $ ones , $ i , $ j , $ k ) ) ) ; return $ ans ; } $ mat = array ( array ( 0 , 0 , 1 ) , array ( 0 , 0 , 1 ) , array ( 1 , 0 , 1 ) ) ; echo sol ( $ mat ) ; ? >