Maximum Sum Path in Two Arrays

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:

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!

Software Developer

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store