Find a specific pair in Matrix | An efficient method to find maximum value of mat1 [ d ] - ma [ a ] [ b ] such that c > a and d > b ; The function returns maximum value A ( c , d ) - A ( a , b ) over all choices of indexes such that both c > a and d > b . ; stores maximum value ; maxArr [ i ] [ j ] stores max of elements in matrix from ( i , j ) to ( N - 1 , N - 1 ) ; last element of maxArr will be same 's as of  the input matrix ; preprocess last row Initialize max ; preprocess last column Initialize max ; preprocess rest of the matrix from bottom ; Update maxValue ; set maxArr ( i , j ) ; Driver code
import java . io . * ; import java . util . * ; class GFG { static int findMaxValue ( int N , int mat [ ] [ ] ) { int maxValue = Integer . MIN_VALUE ; int maxArr [ ] [ ] = new int [ N ] [ N ] ; maxArr [ N - 1 ] [ N - 1 ] = mat [ N - 1 ] [ N - 1 ] ; int maxv = mat [ N - 1 ] [ N - 1 ] ; for ( int j = N - 2 ; j >= 0 ; j -- ) { if ( mat [ N - 1 ] [ j ] > maxv ) maxv = mat [ N - 1 ] [ j ] ; maxArr [ N - 1 ] [ j ] = maxv ; } maxv = mat [ N - 1 ] [ N - 1 ] ; for ( int i = N - 2 ; i >= 0 ; i -- ) { if ( mat [ i ] [ N - 1 ] > maxv ) maxv = mat [ i ] [ N - 1 ] ; maxArr [ i ] [ N - 1 ] = maxv ; } for ( int i = N - 2 ; i >= 0 ; i -- ) { for ( int j = N - 2 ; j >= 0 ; j -- ) { if ( maxArr [ i + 1 ] [ j + 1 ] - mat [ i ] [ j ] > maxValue ) maxValue = maxArr [ i + 1 ] [ j + 1 ] - mat [ i ] [ j ] ; maxArr [ i ] [ j ] = Math . max ( mat [ i ] [ j ] , Math . max ( maxArr [ i ] [ j + 1 ] , maxArr [ i + 1 ] [ j ] ) ) ; } } return maxValue ; } public static void main ( String [ ] args ) { int N = 5 ; int mat [ ] [ ] = { { 1 , 2 , - 1 , - 4 , - 20 } , { - 8 , - 3 , 4 , 2 , 1 } , { 3 , 8 , 6 , 1 , 3 } , { - 4 , - 1 , 1 , 7 , - 6 } , { 0 , - 4 , 10 , - 5 , 1 } } ; System . out . print ( " Maximum ▁ Value ▁ is ▁ " + findMaxValue ( N , mat ) ) ; } }