Find a specific pair in Matrix | An efficient method to find maximum value of mat [ 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
< ? php $ N = 5 ; function findMaxValue ( $ mat ) { global $ N ; $ maxValue = PHP_INT_MIN ; $ maxArr [ $ N ] [ $ N ] = array ( ) ; $ maxArr [ $ N - 1 ] [ $ N - 1 ] = $ mat [ $ N - 1 ] [ $ N - 1 ] ; $ maxv = $ mat [ $ N - 1 ] [ $ N - 1 ] ; for ( $ 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 ( $ i = $ N - 2 ; $ i >= 0 ; $ i -- ) { if ( $ mat [ $ i ] [ $ N - 1 ] > $ maxv ) $ maxv = $ mat [ $ i ] [ $ N - 1 ] ; $ maxArr [ $ i ] [ $ N - 1 ] = $ maxv ; } for ( $ i = $ N - 2 ; $ i >= 0 ; $ i -- ) { for ( $ 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 ] = max ( $ mat [ $ i ] [ $ j ] , max ( $ maxArr [ $ i ] [ $ j + 1 ] , $ maxArr [ $ i + 1 ] [ $ j ] ) ) ; } } return $ maxValue ; } $ mat = array ( array ( 1 , 2 , -1 , -4 , -20 ) , array ( -8 , -3 , 4 , 2 , 1 ) , array ( 3 , 8 , 6 , 1 , 3 ) , array ( -4 , -1 , 1 , 7 , -6 ) , array ( 0 , -4 , 10 , -5 , 1 ) ) ; echo " Maximum ▁ Value ▁ is ▁ " . findMaxValue ( $ mat ) ; ? >