Maximum Sum Path in Two Arrays

Maximum Sum Path in Two Arrays - GeeksforGeeks

This is a good question, So decided to solve it.

Given two sorted arrays, such that the arrays may have some common elements. Find the sum of the maximum sum path to reach from the beginning of any array to end of any of the two arrays. We can switch from one array to another array only at common elements.
Note: The common elements do not have to be at the same indexes.
Expected Time Complexity: O(m+n), where m is the number of elements in ar1[] and n is the number of elements in ar2[].

Examples:

Input: ar1[] = {2, 3, 7, 10, 12}
       ar2[] = {1, 5, 7, 8}
Output: 35

Explanation: 35 is sum of 1 + 5 + 7 + 10 + 12.
We start from the first element of arr2 which is 1, then we
move to 5, then 7.  From 7, we switch to ar1 (as 7 is common)
and traverse 10 and 12.

Input: ar1[] = {10, 12}
       ar2 = {5, 7, 9}
Output: 22

Explanation: 22 is the sum of 10 and 12.
Since there is no common element, we need to take all 
elements from the array with more sum.

Input: ar1[] = {2, 3, 7, 10, 12, 15, 30, 34}
        ar2[] = {1, 5, 7, 8, 10, 15, 16, 19}
Output: 122

Explanation: 122 is sum of 1, 5, 7, 8, 10, 12, 15, 30, 34

Here comes the approach:

1. Our goal is to reach the common element from both arrays.
2. So take 2 variables, say sum1 and sum2 keep track of elements sum from both the array till we reach common element.
3. As we reach a common element, find the maximum between the 2 sums, and update the result. Also as sum1 and sum2 work is done at this point again initialize them to 0, and perform the same operation.
4. while in step 3 do put the check also if elements of both arrays are the same then store them in the result and increase the counter for both.
5. In the end, if Array1 or Array2 whichever is not traversed till the end put all elements as result(check for max sum also) to the result variable.

Let's look at the code and things will be more clear.

package com.geeks.array;
public class MaximumSumPathInTwoArray {
public static void main(String[] args) {
     int arr1[] = {2, 3, 7, 10, 12 };
     int arr2[] = {1, 5, 7, 8};
     findMax(arr1, arr2);
}
   public static void findMax(int arr1[], int arr2[]) {
      int sum1 = 0;int sum2 = 0;int result = 0;
      int i = 0, j = 0;
        while (i < arr1.length && j < arr2.length) {
         if (arr1[i] < arr2[j]) {
            sum1 += arr1[i];
             i++;
         } else if (arr1[i] > arr2[j]) {
            sum2 += arr2[j];
             j++;
         } else {
          result += Math.max(sum2, sum1);
          sum1 = sum2 = 0;
          while (arr1[i] == arr2[j] && i < arr1.length && j <                     arr2.length) {
           result += arr1[i];
           i++;j++;
         }
      }
    }
while (i < arr1.length) {
sum1 += arr1[i];
i++;
}
while (j < arr2.length) {
sum2 += arr2[j];
j++;
}
result += Math.max(sum1, sum2);
System.out.println(result);
}
}

Happy Coding!