Given two sorted array of integers, find a maximum sum path involving elements of both arrays whose sum is maximum. We can start from either arrays but we can switch between arrays only through its common elements.
import java.util.*;
public class SortedArraysMergeSum {
public static void main(String args[]) {
SortedArraysMergeSum mergeSum = new SortedArraysMergeSum();
int[][] input1 = {
null,
{},
{1},
{2,3,10,13,13,18,20},
{3,6,7,8,10,12,15,18,100}
};
int[][] input2 = {
null,
{},
{1,3},
{10,11,11,12,13,19,20},
{1,2,3,5,7,9,10,11,15,16,18,25,50}
};
for(int i=0; i< input1.length; i++) {
int sum = 10;
System.out.println("Input: " + Arrays.toString(input1[i]) + ", " + Arrays.toString(input2[i]) + " Result: " + mergeSum.find(input1[i], input2[i]));
}
}
private int find(int[] input1, int[] input2) {
if(input1 == null && input2 == null) {
return -1;
}
int sum = 0;
if (input1 == null) {
for(int i=1; i<input1.length; i++) {
if(input1[i] != input1[i-1]) {
sum += input1[i];
}
}
return sum;
}
if (input2 == null) {
for(int j=1; j<input2.length; j++) {
if(input2[j] != input2[j-1]) {
sum += input2[j];
}
}
return sum;
}
int i=0;
int j=0;
int sum1 = 0;
int sum2 = 0;
while(i < input1.length && j < input2.length) {
while(i < input1.length -1 && input1[i] == input1[i+1]) {
sum1 += input1[i++];
}
while(j < input2.length -1 && input2[j] == input2[j+1]) {
sum2 += input2[j++];
}
if(input1[i] < input2[j]) {
sum1 += input2[j++];
} else if (input1[i] > input2[j]) {
sum2 += input1[i++];
} else {
sum += Math.max(sum1, sum2) + input1[i];
sum1 = 0;
sum2 = 0;
i++; j++;
}
}
while (i < input1.length){
sum += input1[i++];
}
while (j < input2.length){
sum += input2[j++];
}
return sum;
}
}