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
import sys NEW_LINE N = 5 NEW_LINE def findMaxValue ( mat ) : NEW_LINE INDENT maxValue = - sys . maxsize - 1 NEW_LINE maxArr = [ [ 0 for x in range ( N ) ] for y in range ( N ) ] NEW_LINE maxArr [ N - 1 ] [ N - 1 ] = mat [ N - 1 ] [ N - 1 ] NEW_LINE maxv = mat [ N - 1 ] [ N - 1 ] ; NEW_LINE for j in range ( N - 2 , - 1 , - 1 ) : NEW_LINE INDENT if ( mat [ N - 1 ] [ j ] > maxv ) : NEW_LINE INDENT maxv = mat [ N - 1 ] [ j ] NEW_LINE DEDENT maxArr [ N - 1 ] [ j ] = maxv NEW_LINE DEDENT maxv = mat [ N - 1 ] [ N - 1 ] ; NEW_LINE for i in range ( N - 2 , - 1 , - 1 ) : NEW_LINE INDENT if ( mat [ i ] [ N - 1 ] > maxv ) : NEW_LINE INDENT maxv = mat [ i ] [ N - 1 ] NEW_LINE DEDENT maxArr [ i ] [ N - 1 ] = maxv NEW_LINE DEDENT for i in range ( N - 2 , - 1 , - 1 ) : NEW_LINE INDENT for j in range ( N - 2 , - 1 , - 1 ) : NEW_LINE INDENT if ( maxArr [ i + 1 ] [ j + 1 ] - mat [ i ] [ j ] > maxValue ) : NEW_LINE INDENT maxValue = ( maxArr [ i + 1 ] [ j + 1 ] - mat [ i ] [ j ] ) NEW_LINE DEDENT maxArr [ i ] [ j ] = max ( mat [ i ] [ j ] , max ( maxArr [ i ] [ j + 1 ] , maxArr [ i + 1 ] [ j ] ) ) NEW_LINE DEDENT DEDENT return maxValue NEW_LINE DEDENT 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 ] ] NEW_LINE print ( " Maximum ▁ Value ▁ is " , findMaxValue ( mat ) ) NEW_LINE