Let us consider the following example
Array1 = {1, 5, 9, 15}
Array2 = {7, 9, 12}
The maximum sum is 7 + 9 + 15 = 31
Similarly let us examine a little more complex example
Array1 = {1, 3, 7, 10, 15, 19}
Array2 = {2, 4, 6, 7, 9, 15, 20}
The maximum sum is 2 + 4 + 6 + 7 + 10 + 15 + 20 = 64
This problem is similar to finding the common elements between two sorted arrays and also similar to the merge procedure in merge sort. You can check out my previous post on this.
Start with two indices pointing to the beginning of two arrays.
We maintain two variables sum1, sum2 to keep track of the partial sum. Compare the two elements, move the index with lesser element forward and add it to it’s corresponding sum.
We do this until we find an equal element; at this point we add the maximum of two sums to a global maxSum variable and repeat the same procedure.
Let us trace the algorithm for the first example
- sum1 = 0, sum2 = 0, ind1 = 0, ind2 = 0, maxSum = 0
- sum1 = 1, sum2 = 0, ind1 = 1, ind2 = 0, maxSum = 0
- sum1 = 6, sum2 = 0, ind1 = 2, ind2 = 0, maxSum = 0
- sum1 = 6, sum2 = 7, ind1 = 2, ind2 = 1, maxSum = 0
- sum1 = 0, sum2 = 0, ind1 = 3, ind2 = 2, maxSum = 7
- sum1 = 15, sum2 = 12, ind1 = 3, ind2 = 2, maxSum = 16
- We reached the end; update maxSum = 16+15 = 31
Here is the C++ code for the same. It runs in O(m+n) time where m, n are the lengths of the two arrays respectively.