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.

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_x*i* denotes the sum of elements between two common elements in array X. Similarly, sum_y*i* denotes the sum of elements between two common elements in array Y. For each pair (sum_x*i*, sum_y*i*), we include max(sum_x*i*, sum_y*i*) 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 –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
#include<iostream> using namespace std; // Function to find maximum sum path in two given arrays // Below code is similar to merge routine of mergesort algorithm int maxSum(int X[], int Y[], int m, int n) { int sum = 0; int sum_x = 0, sum_y = 0; // i and j denotes current index of X and Y respectively int i = 0, j = 0; // loop till X and Y are not empty while (i < m && j < n) { // to handle duplicate elements in X while (i < m-1 && X[i] == X[i+1]) sum_x += X[i++]; // to handle duplicate elements in Y while (j < n-1 && Y[j] == Y[j+1]) sum_y += Y[j++]; // if current element of Y is less than current element of X if (Y[j] < X[i]) { sum_y += Y[j]; j++; } // if current element of X is less than current element of Y else if (X[i] < Y[j]) { sum_x += X[i]; i++; } else // if (X[i] == Y[j]) { // consider maximum sum and include value of current cell sum += max(sum_x, sum_y) + X[i]; // move both indices by 1 position i++, j++; // reset both sums sum_x = 0, sum_y = 0; } } // process remaining elements of X (if any) while (i < m) sum += X[i++]; // process remaining elements of Y (if any) while (j < n) sum += Y[j++]; return sum; } // main function int main() { int X[] = { 3, 6, 7, 8, 10, 12, 15, 18, 100 }; int Y[] = { 1, 2, 3, 5, 7, 9, 10, 11, 15, 16, 18, 25, 50 }; int m = sizeof(X)/sizeof(X[0]); int n = sizeof(Y)/sizeof(Y[0]); cout << "Maximum sum is " << maxSum(X, Y, m, n); return 0; } |

`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

Line No. 18 and 22

Line No. 18:

while (i < m && X[i] == X[i+1])Shouldn't it be

i < m - 1instead ofi < mbecause ifi == m - 1, X[i+1]would point to range outside the arrayAbhishek, thanks a lot for bringing this issue to our notice. We will update the code. Happy coding 🙂