Max sum path in two Array

Max sum path in two Array

  June 28, 2018    

---

Problem:

Given two sorted arrays such the arrays may have some common elements.
Find the sum of the maximum sum path to reach from beginning of any array to end of any of the two arrays. We can start from any array and switch from one array to another array only at common elements.

Input:

1
5 5
1 2 3 4 5
5 6 7 8 9 

Output
45

Explanation:

1+2+3+4+5+6+7+8+9=45

Intuition:

If we look closer to the problem , it is like merge sort merge Function.
We have to maintain 2 variables for sum of both array.
When we are having common element we can choose any sum and again follow process.

Code:

import java.util.*;
import java.lang.*;
import java.io.*;
class maxSumpathTwoArray
 {
  public static int fn(int a[],int b[],int n,int m)
  {
    int sum1=0,sum2=0;
    int res=0,i=0,j=0;
    while(i<n && j<m)
    {
      if(a[i]==b[j])
      {
        res+=Math.max(sum1,sum2)+a[i];
        sum1=sum2=0;
        ++i;
        ++j;
      }
      else if(a[i]<b[j])
      sum1+=a[i++];
      else
      sum2+=b[j++];
    }
    while(i<n)
    sum1+=a[i++];

    while(j<m)
    sum2+=b[j++];
    return res+Math.max(sum1,sum2);
  }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    int n=ab.nextInt();
    int m=ab.nextInt();
    int arr[]=new int[n];
    int arr2[]=new int[m];
    for(int i=0;i<n;++i)
    arr[i]=ab.nextInt();
    for(int i=0;i<m;++i)
    arr2[i]=ab.nextInt();
    System.out.println(fn(arr,arr2,n,m));
}
}
}