# 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: 35Explanation: 35 is sum of 1 + 5 + 7 + 10 + 12.We start from the first element of arr2 which is 1, then wemove 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: 22Explanation: 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: 122Explanation: 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!

## More from Vipul Gupta

Software Developer