# Find maximum sum path involving elements of given arrays

Given two sorted array of integers, find a maximum sum path involving elements of both arrays whose sum is maximum. We can start from either arrays but we can switch between arrays only through its common elements.

For example,

Input:
X = { 3, 6, 7, 8, 10, 12, 15, 18, 100 }
Y = { 1, 2, 3, 5, 7, 9, 10, 11, 15, 16, 18, 25, 50 }

The maximum sum path is
1 —> 2 —> 3 —> 6 —> 7 —> 9 —> 10 —> 12 —> 15 —> 16 —> 18 —> 100

The maximum sum is 199

The idea is very simple. We calculate sum between common elements present in the both arrays and include the maximum sum in the output.

For example, consider below arrays X and Y having four common elements A, B, C, D.

X[]: sum_x1 .., A, .. sum_x2 .., B, .. sum_x3 .., C, .. sum_x4 .., D, .. sum_x5
Y[]: sum_x1 .., A, .. sum_y2 .., B, .. sum_y3 .., C, .. sum_y4 .., D, .. sum_y5

Here sum_xi denotes the sum of elements between two common elements in array X. Similarly, sum_yi denotes the sum of elements between two common elements in array Y. For each pair (sum_xi, sum_yi), we include max(sum_xi, sum_yi) in the solution. i.e.

Result = max(sum_x1, sum_y1) + A + max(sum_x2, sum_y2) + B + max(sum_x3, sum_y3)
+ C + max(sum_x4, sum_y4) + D + max(sum_x5, sum_y5)

## C

Output:

Maximum sum is 199

## Java

Output:

Maximum sum is 199

The time complexity of above solution is O(n + m) and auxiliary space used by the program is O(1).

Exercise:

1. Print maximum sum path (Hint – use std::vectors)

2. Use recursion to solve this problem.

3. Modify above code to find maximum sum path by traversing from end of the array.     (1 votes, average: 5.00 out of 5) Loading...

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂 Subscribe
Notify of Guest
Abhishek

Line No. 18 and 22

Line No. 18:
while (i < m && X[i] == X[i+1])
Shouldn't it be i < m - 1 instead of i < m because if i == m - 1, X[i+1] would point to range outside the array Guest

For the given example, does it still work if the “left-over” sum is larger than the difference of all the (sum_xi – sum_yi) combined? For example, what if the last element in Y array is 1000 instead of 50?