Make delicious recipes!

Maximum sum path in two sorted arrays


Problem: Given two sorted arrays, find a path such that it uses elements from either of the arrays at a time and sum of whose elements is maximum.

Only condition to satisfy is that you can change from one array to another only when the elements are matching.

Example: Given following two arrays:

arr1 = [1, 2, 8, 9, 10, 15, 20]

arr2 = [7, 8, 10, 11, 20, 25]

Then maximum sum path = 7, 8, 9, 10, 15, 20, 25

Some other paths possible are: 1,2,8,10,11,20 or 7,8,10,15,20

But since the sum of their elements is not maximum, they do not form the answer.


Solution: We cannot switch array while we are in between one pair of equal points and the next pair of equal points. So we need to choose an array which will yield the maximum sum between two pairs of equals. If we sum both arrays till the next pair of equal points, and choose the maximum sum sub-array on arriving at the next equal pair, we could find the path with maximum sum.

int maxPathSum(int arr1[], int arr2[])
{
    int i = 0;
    int j = 0;
    int sum1 = 0;
    int sum2 = 0;
    int result = 0;
    int m = arr1.length;
    int n = arr2.length;
 
    // This part is very similar to merge sort
    while (i < m && j < n)
    {
        if (arr1[i] < arr2[j])
            sum1 += arr1[i++];
 
        else if (arr1[i] > arr2[j])
            sum2 += arr2[j++];
 
        else  // Found a common point
        {
            result += max(sum1, sum2);
            sum1 = 0;
            sum2 = 0;
 
            while (i < m &&  j < n && arr1[i] == arr2[j])
            {
                result = result + arr1[i];
                i++;
                j++;
            }
        }
    }
 
    // The loop ends when one of the array reached its end.
    // That means we still have to choose the array whose elements will end the
    // maximum-sum-path (since last pair of equals)
    while (i < m)
        sum1  +=  arr1[i++];
    while (j < n)
        sum2 +=  arr2[j++];
 
    result +=  max(sum1, sum2);
 
    return result;
}






Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal