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

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