Maximum points collected by two persons allowed to meet once | Python program to find maximum points that can be collected by two persons in a matrix . ; To store points collected by Person P1 when he / she begins journy from start and from end . ; To store points collected by Person P2 when he / she begins journey from start and from end . ; Table for P1 's journey from  start to meeting cell ; Table for P1 's journey from  end to meet cell ; Table for P2 's journey from start to meeting cell ; Table for P2 's journey from end to meeting cell ; Now iterate over all meeting positions ( i , j ) ;
M = 3 NEW_LINE N = 3 NEW_LINE def findMaxPoints ( A ) : NEW_LINE INDENT P1S = [ [ 0 for i in range ( N + 2 ) ] for j in range ( M + 2 ) ] NEW_LINE P1E = [ [ 0 for i in range ( N + 2 ) ] for j in range ( M + 2 ) ] NEW_LINE P2S = [ [ 0 for i in range ( N + 2 ) ] for j in range ( M + 2 ) ] NEW_LINE P2E = [ [ 0 for i in range ( N + 2 ) ] for j in range ( M + 2 ) ] NEW_LINE for i in range ( 1 , N + 1 ) : NEW_LINE INDENT for j in range ( 1 , M + 1 ) : NEW_LINE INDENT P1S [ i ] [ j ] = max ( P1S [ i - 1 ] [ j ] , P1S [ i ] [ j - 1 ] ) + A [ i - 1 ] [ j - 1 ] NEW_LINE DEDENT DEDENT for i in range ( N , 0 , - 1 ) : NEW_LINE INDENT for j in range ( M , 0 , - 1 ) : NEW_LINE INDENT P1E [ i ] [ j ] = max ( P1E [ i + 1 ] [ j ] , P1E [ i ] [ j + 1 ] ) + A [ i - 1 ] [ j - 1 ] NEW_LINE DEDENT DEDENT for i in range ( N , 0 , - 1 ) : NEW_LINE INDENT for j in range ( 1 , M + 1 ) : NEW_LINE INDENT P2S [ i ] [ j ] = max ( P2S [ i + 1 ] [ j ] , P2S [ i ] [ j - 1 ] ) + A [ i - 1 ] [ j - 1 ] NEW_LINE DEDENT DEDENT for i in range ( 1 , N + 1 ) : NEW_LINE INDENT for j in range ( M , 0 , - 1 ) : NEW_LINE INDENT P2E [ i ] [ j ] = max ( P2E [ i - 1 ] [ j ] , P2E [ i ] [ j + 1 ] ) + A [ i - 1 ] [ j - 1 ] NEW_LINE DEDENT DEDENT ans = 0 NEW_LINE for i in range ( 2 , N ) : NEW_LINE INDENT for j in range ( 2 , M ) : NEW_LINE INDENT op1 = P1S [ i ] [ j - 1 ] + P1E [ i ] [ j + 1 ] + P2S [ i + 1 ] [ j ] + P2E [ i - 1 ] [ j ] NEW_LINE op2 = P1S [ i - 1 ] [ j ] + P1E [ i + 1 ] [ j ] + P2S [ i ] [ j - 1 ] + P2E [ i ] [ j + 1 ] NEW_LINE ans = max ( ans , max ( op1 , op2 ) ) NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT / * input the calories burnt matrix * / NEW_LINE A = [ [ 100 , 100 , 100 ] , [ 100 , 1 , 100 ] , [ 100 , 100 , 100 ] ] NEW_LINE print ( " Max ▁ Points ▁ : ▁ " , findMaxPoints ( A ) ) NEW_LINE