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

Download   Run Code

Output:

Maximum sum is 199

Java

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.
 

1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)
Loading...

 
Thanks for reading.

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 🙂
 



Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Abhishek
Guest

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

Carol
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?