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;
}
Got a thought to share or found a bug in the code? We'd love to hear from you:
