Maximum Sum Path in Two Arrays | This function returns the sum of elements on maximum path from beginning to end ; initialize indexes for ar1 [ ] and ar2 [ ] ; Initialize result and current sum through ar1 [ ] and ar2 [ ] ; Below 3 loops are similar to merge in merge sort ; Add elements of ar1 [ ] to sum1 ; Add elements of ar2 [ ] to sum2 ; we reached a common point ; Take the maximum of two sums and add to result ; update sum1 and sum2 to be considered fresh for next elements ; update i and j to move to next element in each array ; Add remaining elements of ar1 [ ] ; Add remaining elements of b [ ] ; Add maximum of two sums of remaining elements ; Driver code ; Function call
def maxPathSum ( ar1 , ar2 , m , n ) : NEW_LINE INDENT i , j = 0 , 0 NEW_LINE result , sum1 , sum2 = 0 , 0 , 0 NEW_LINE while ( i < m and j < n ) : NEW_LINE INDENT if ar1 [ i ] < ar2 [ j ] : NEW_LINE INDENT sum1 += ar1 [ i ] NEW_LINE i += 1 NEW_LINE DEDENT elif ar1 [ i ] > ar2 [ j ] : NEW_LINE INDENT sum2 += ar2 [ j ] NEW_LINE j += 1 NEW_LINE DEDENT else : NEW_LINE INDENT result += max ( sum1 , sum2 ) + ar1 [ i ] NEW_LINE sum1 = 0 NEW_LINE sum2 = 0 NEW_LINE i += 1 NEW_LINE j += 1 NEW_LINE DEDENT DEDENT while i < m : NEW_LINE INDENT sum1 += ar1 [ i ] NEW_LINE i += 1 NEW_LINE DEDENT while j < n : NEW_LINE INDENT sum2 += ar2 [ j ] NEW_LINE j += 1 NEW_LINE DEDENT result += max ( sum1 , sum2 ) NEW_LINE return result NEW_LINE DEDENT ar1 = [ 2 , 3 , 7 , 10 , 12 , 15 , 30 , 34 ] NEW_LINE ar2 = [ 1 , 5 , 7 , 8 , 10 , 15 , 16 , 19 ] NEW_LINE m = len ( ar1 ) NEW_LINE n = len ( ar2 ) NEW_LINE print " Maximum ▁ sum ▁ path ▁ is " , maxPathSum ( ar1 , ar2 , m , n ) NEW_LINE