# Find maximum sum path by involving elements from two arrays

The idea is to do something similar to merge process of merge sort. This involves calculating the sum of elements between all common points of both arrays. Whenever there is a common point, compare the two sums and add the maximum of two to the result.

Input:

X = { 3, 6, 7, 8, 10, 12, 15, 18, 100 }
Y = { 1, 2, 3, 5, 7, 9, 10, 11, 15, 16, 18, 25, 50 }

The maximum sum path is:

1 → 2 → 3 → 6 → 7 → 9 → 10 → 12 → 15 → 16 → 18 → 100

The maximum sum is 199

Complexity :- Time Complexity O(n+m) Space Complexity O(1)

`class Main {// Function to find the maximum sum path in two given arrays.// The code is similar to the merge routine of the merge sort algorithm public static int findMaxSum(int[] X, int[] Y) {   int sum = 0;   int sum_x = 0, sum_y = 0;   int m = X.length, n = Y.length;   // `i` and `j` denotes the current index of `X` and `Y`, respectively   int i = 0, j = 0;   // loop till `X` and `Y` are empty   while (i < m && j < n) {     // to handle the duplicate elements in `X`   while (i < m-1 && X[i] == X[i+1]) {     sum_x += X[i++];   }// to handle the duplicate elements in `Y`   while (j < n-1 && Y[j] == Y[j+1]) {    sum_y += Y[j++];   }// if the current element of `Y` is less than the current element of `X`   if (Y[j] < X[i]) {     sum_y += Y[j];    j++;   }// if the current element of `X` is less than the current element of `Y`   else if (X[i] < Y[j]) {    sum_x += X[i];    i++;   }   else // if (X[i] == Y[j]) {    // consider the maximum sum and include the current cell's value    sum += Integer.max(sum_x, sum_y) + X[i];   // move both indices by 1 position   i++;   j++;// reset both sums   sum_x = 0;   sum_y = 0;  }}// process the remaining elements of `X` (if any)    while (i < m)     sum_x += X[i++];// process the remaining elements of `Y` (if any)   while (j < n)     sum_y += Y[j++];    sum += Integer.max(sum_x, sum_y);    return sum;  } public static void main(String[] args) {   int[] X = { 3, 6, 7, 8, 10, 12, 15, 18, 100 };   int[] Y = { 1, 2, 3, 5, 7, 9, 10, 11, 15, 16, 18, 25, 50 };   System.out.print("The maximum sum is " + findMaxSum(X, Y)); }}Output:The maximum sum is 199`

we can do it in recursive approach by using memoization concept. Try it your self. It will take O(n) time and space.

Full Stack Software Developer| Programming enthusiast | Loves DS-Algo and System Design

## More from Sivareddy Uppathi

Full Stack Software Developer| Programming enthusiast | Loves DS-Algo and System Design

## IPFS Cluster with Docker

Get the Medium app