Maximum sum submatrix | Function to find maximum continuous maximum sum in the array ; Stores current and maximum sum ; Traverse the array v ; Add the value of the current element ; Update the maximum sum ; Return the maximum sum ; Function to find the maximum submatrix sum ; Store the rows and columns of the matrix ; Create an auxiliary matrix ; Traverse the matrix , prefix and initialize it will all 0 s ; Calculate prefix sum of all rows of matrix A [ ] [ ] and store in matrix prefix [ ] ; Update the prefix [ ] [ ] ; Store the maximum submatrix sum ; Iterate for starting column ; Iterate for last column ; To store current array elements ; Traverse every row ; Store the sum of the kth row ; Update the prefix sum ; Push it in a vector ; Update the maximum overall sum ; Print the answer ; Driver Code ; Function Call
function kadane ( v ) { let currSum = 0 ; let maxSum = Number . MIN_VALUE ; for ( let i = 0 ; i < v . length ; i ++ ) { currSum += v [ i ] ; if ( currSum > maxSum ) { maxSum = currSum ; } if ( currSum < 0 ) { currSum = 0 ; } } return maxSum ; } function maxSubmatrixSum ( A ) { let r = A . length ; let c = A [ 0 ] . length ; let prefix = new Array ( r ) ; for ( let i = 0 ; i < r ; i ++ ) { prefix [ i ] = new Array ( c ) ; for ( let j = 0 ; j < c ; j ++ ) { prefix [ i ] [ j ] = 0 ; } } for ( let i = 0 ; i < r ; i ++ ) { for ( let j = 0 ; j < c ; j ++ ) { if ( j == 0 ) prefix [ i ] [ j ] = A [ i ] [ j ] ; else prefix [ i ] [ j ] = A [ i ] [ j ] + prefix [ i ] [ j - 1 ] ; } } let maxSum = Number . MIN_VALUE ; for ( let i = 0 ; i < c ; i ++ ) { for ( let j = i ; j < c ; j ++ ) { let v = [ ] ; for ( let k = 0 ; k < r ; k ++ ) { let el = 0 ; if ( i == 0 ) el = prefix [ k ] [ j ] ; else el = prefix [ k ] [ j ] - prefix [ k ] [ i - 1 ] ; v . push ( el ) ; } maxSum = Math . max ( maxSum , kadane ( v ) ) ; } } document . write ( maxSum + " " ) ; } let matrix = [ [ 0 , - 2 , - 7 , 0 ] , [ 9 , 2 , - 6 , 2 ] , [ - 4 , 1 , - 4 , 1 ] , [ - 1 , 8 , 0 , - 2 ] ] ; maxSubmatrixSum ( matrix ) ;