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++ implementation –
 

Download   Run Code

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.
 

Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
Abhishek
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

wpDiscuz