Maximize the binary matrix by filpping submatrix once | Javascript 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 function
let R = 3 ; let 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 ) { let ans = 0 ; let val = 0 ; let ones = new Array ( R + 1 ) ; for ( var i = 0 ; i < ones . length ; i ++ ) { ones [ i ] = new Array ( 2 ) ; } for ( var i = 0 ; i < ones . length ; i ++ ) { for ( var j = 0 ; j < ones . length ; j ++ ) { ones [ i ] [ j ] = 0 ; } } for ( let i = 1 ; i <= R ; i ++ ) for ( let 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 ( let k = 1 ; k <= Math . min ( R , C ) ; k ++ ) for ( let i = 1 ; i + k - 1 <= R ; i ++ ) for ( let j = 1 ; j + k - 1 <= C ; j ++ ) ans = Math . max ( ans , ( ones [ R ] [ C ] + k * k - 2 * cal ( ones , i , j , k ) ) ) ; return ans ; } let mat = [ [ 0 , 0 , 1 ] , [ 0 , 0 , 1 ] , [ 1 , 0 , 1 ] ] ; document . write ( sol ( mat ) ) ;