Close

# Maximum sum path in two sorted arrays

Given two sorted arrays of size M and N, Find a sequence of elements from both the arrays whose sum is maximum. The sequence can begin with any of the two arrays and can jump from one array to another array if there is a common element.

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.

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.