Maximize the binary matrix by filpping submatrix once | Python 3 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
R = 3 NEW_LINE C = 3 NEW_LINE def cal ( ones , x , y , k ) : NEW_LINE INDENT 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 ] ) NEW_LINE DEDENT def sol ( mat ) : NEW_LINE INDENT ans = 0 NEW_LINE ones = [ [ 0 for i in range ( C + 1 ) ] for i in range ( R + 1 ) ] NEW_LINE for i in range ( 1 , R + 1 , 1 ) : NEW_LINE INDENT for j in range ( 1 , C + 1 , 1 ) : NEW_LINE INDENT ones [ i ] [ j ] = ( ones [ i - 1 ] [ j ] + ones [ i ] [ j - 1 ] - ones [ i - 1 ] [ j - 1 ] + ( mat [ i - 1 ] [ j - 1 ] == 1 ) ) NEW_LINE DEDENT DEDENT for k in range ( 1 , min ( R , C ) + 1 , 1 ) : NEW_LINE INDENT for i in range ( 1 , R - k + 2 , 1 ) : NEW_LINE INDENT for j in range ( 1 , C - k + 2 , 1 ) : NEW_LINE INDENT ans = max ( ans , ( ones [ R ] [ C ] + k * k - 2 * cal ( ones , i , j , k ) ) ) NEW_LINE DEDENT DEDENT DEDENT return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT mat = [ [ 0 , 0 , 1 ] , [ 0 , 0 , 1 ] , [ 1 , 0 , 1 ] ] NEW_LINE print ( sol ( mat ) ) NEW_LINE DEDENT