Maximum sum submatrix | Java program for the above approach ; 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
import java . util . * ; class GFG { static int kadane ( Vector < Integer > v ) { int currSum = 0 ; int maxSum = Integer . MIN_VALUE ; for ( int i = 0 ; i < ( int ) v . size ( ) ; i ++ ) { currSum += v . get ( i ) ; if ( currSum > maxSum ) { maxSum = currSum ; } if ( currSum < 0 ) { currSum = 0 ; } } return maxSum ; } static void maxSubmatrixSum ( int [ ] [ ] A ) { int r = A . length ; int c = A [ 0 ] . length ; int [ ] [ ] prefix = new int [ r ] [ ] ; for ( int i = 0 ; i < r ; i ++ ) { prefix [ i ] = new int ; for ( int j = 0 ; j < c ; j ++ ) { prefix [ i ] [ j ] = 0 ; } } for ( int i = 0 ; i < r ; i ++ ) { for ( int 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 ] ; } } int maxSum = Integer . MIN_VALUE ; for ( int i = 0 ; i < c ; i ++ ) { for ( int j = i ; j < c ; j ++ ) { Vector < Integer > v = new Vector < Integer > ( ) ; for ( int k = 0 ; k < r ; k ++ ) { int el = 0 ; if ( i == 0 ) el = prefix [ k ] [ j ] ; else el = prefix [ k ] [ j ] - prefix [ k ] [ i - 1 ] ; v . add ( el ) ; } maxSum = Math . max ( maxSum , kadane ( v ) ) ; } } System . out . print ( maxSum + "NEW_LINE"); } public static void main ( String [ ] args ) { int [ ] [ ] matrix = { { 0 , - 2 , - 7 , 0 } , { 9 , 2 , - 6 , 2 } , { - 4 , 1 , - 4 , 1 } , { - 1 , 8 , 0 , - 2 } } ; maxSubmatrixSum ( matrix ) ; } }