CareerCup

#include<iostream>

using namespace std;


int Max(int i, int j)
{
   return i > j ? i : j;
}

int MaxSumPath(int arr1[],int arr2[], int m, int n)
{
    int i = 0;
    int j = 0;

    int max_sum = 0;

    int sum1 = 0;
    int sum2 = 0;

    while(i < m && j < n)
    {
        if(arr1[i] < arr2[j])
        {
           sum1 +=arr1[i];
           i++;
        }
        else if(arr1[i] > arr2[j])
        {
           sum2 +=arr2[j];
           j++;
        }
        else
        {
           max_sum = Max(sum1,sum2) + max_sum;
           sum1 = 0;
           sum2 = 0;
           while(i < m &&  j < n && arr1[i] == arr2[j])
           {
                max_sum = max_sum + arr1[i];
                i++;
                j++;
           }
        }
    }

    while(i < m)
    {
       sum1  = sum1 + arr1[i];
       i++;
    }

    while(j < n)
    {
       sum2 = sum2 + arr2[j];
       j++;
    }

    max_sum = max_sum + Max(sum1,sum2);
    return max_sum;
}

int main()
{

   int arr1[] = {3, 5, 7, 9, 20, 25, 30, 40, 55, 56, 57, 60, 62}; 
   int arr2[] = {1, 4, 7, 11, 14, 25, 44, 47, 55, 57,100};
   int sum = MaxSumPath(arr1,arr2,13,11);
   cout<<sum;
   return 0;
}

Hi All

This is just a slightly different take on the merge routine in merge sort. It does not require recursion nor does it require dynamic programming. It is implemented iteratively, with the efficiency being O(n+m), where n and m are the sizes of the two arrays.

The basic idea is as follows:
1) Let A and B denote the two arrays
2) Let idx1 be the current index of the array A, and let idx2 be the current index of array B
3) While the element at the current index of A (i.e. A[idx1]) is less then the element at the current index of B (B[idx2]) increment idx1, and add each element to a running total (call it sumA)
4) Now that A[idx1] > B[idx2], increment idx2 of B until B[idx2] is not less than A[idx1], and also add it to a running total (call it sumB)
5) If at this point, A[idx1] is equal to B[idx2], we have found our intersection point. So add the maximum of sumA and sumB i.e. max(sumA,sumB) to the totalresult. Set sumA and sumB to zero, and repeat the whole process until all the elements in A and B have been examined.

The code for the above is as follows:

int getMax(vector<int>& A, vector<int>& B) {
    int idx1 = 0,
        idx2 = 0,
        sumA = 0,
        sumB = 0,
        total = 0;

    while (idx1 < A.size() || idx2 < B.size()) {
        while (idx2 >= B.size() && idx1 < A.size() || idx1 < A.size() && A[idx1] < B[idx2]) 
            sumA += A[idx1++];

        while (idx1 >= A.size() && idx2 < B.size() || idx2 < B.size() && B[idx2] < A[idx1]) 
            sumB += B[idx2++];

        if (A[idx1] == B[idx2]) {
            if (idx1 < A.size()) sumA += A[idx1++];
            if (idx2 < B.size()) sumB += B[idx2++];
            total += max(sumA, sumB);
            sumA = sumB = 0;
        }
    } 

    total += max(sumA, sumB);

    return total;
}

This works fine for me

public class Seq{

public static void main(String[] args){
 int[] arr1 = {3,5,7,9,20,25,30,40,55,56,57,60,62};
 int[] arr2 = {1,4,7,11,14,25,44,47,55,57,100};

 //int[] arr1 = {2,3,4,5,7,8};
 //int[] arr2 = {1,2,4,6};
  System.out.println(Sum(arr1,arr2,0));
}

public static int Sum(int[] arr1, int[] arr2, int i){
    if(i>=arr1.length && i >= arr2.length) return 0;
    int sum1=0,sum2=0;
    while(i<arr1.length || i<arr2.length){
        sum1 += i < arr1.length ? arr1[i] : 0;
        sum2 += i < arr2.length ? arr2[i] : 0;
        if(i < arr1.length && i<arr2.length && (arr1[i] == arr2[i]))
            {i++;break;}
        i++;
    }
    return Math.max(sum1,sum2) + Sum(arr1,arr2,i);
}

}

Let A[0..n-1] and B[0..m-1] are two arrays.
Segments of A or B = set of subarrays between two intersection points including subarray before first intersection point and subarray after last intersection point.
So if there are K intersection points then we have (K+1) segments each of A and B.
Iterate over all segments, if segment of A has greater sum then choose it else choose segment of B.
We can iterate over segments in O(m+n) time.

sum_subarray_a = 0;
sum_subarray_b = 0;
max_sum = 0;
i = 0;
j = 0;

while ( i < n && j < m ) {
	if (a[i] > b[j]) {
		while( j < m && a[i] > b[j] ) {
			sum_subarray_b += b[j];
			j++;
		}
	} else if ( a[i] < b[j] ) {
		while ( i < n && a[i] < b[j] ) {
			sum_subarray_a += a[i];
			i++;
		} 
	} else {
		max_sum += max(sum_subarray_a, sum_subarray_b) + a[i]; 
		// Why adding a[i] in last statement ? Because we need to add intersection point also in max_sum.
		sum_subarray_a = sum_subarray_b = 0;
		i++;
		j++;
	}
}

max_sum += max( sum_subarray_a + (sum of a[i] to a[n-1]), 
				sum_subarray_b + (sum of b[j] to b[m-1]));
//max_sum is the answer

Recursive Approach to Solve this

Algorithm:
1. whenever the program encounters an intersection point, it goes 2 ways and return the corresponding sums.
2. We will get the maximum sum of these and then add the intersection point and return it.

#include <iostream>
#include <algorithm>
using namespace std;

size_t FindMaxSum(int First[], int Second[], int i, int j, int Flen, int Slen);

int main() {
	// your code goes here
	int First[] = {3,5,7,9,20,25,30,40,55,56,57,60,62};
	int Flen = sizeof(First)/sizeof(First[0]);
	int Second[] = {1,4,7,11,14,25,44,47,55,57,100};
	int Slen = sizeof(Second)/sizeof(Second[0]);
	cout<<"Maximum Sum :"<<FindMaxSum(First,Second,0,0,Flen,Slen);
	return 0;
}

size_t FindMaxSum(int First[], int Second[], int i, int j, int Flen, int Slen)
{
	//Boundary Condition
	if(i >= Flen) return 0;
	
	int Sum = 0;
	
	while(i < Flen && j < Slen)
	{
		if(First[i] == Second[j])
		{
			Sum += First[i] + max(FindMaxSum(First,Second,i+1,j+1,Flen,Slen),FindMaxSum(Second,First,j+1,i+1,Slen,Flen));
			return Sum;
		}
		else if(First[i] < Second[j])
		{
			Sum += First[i];
			i++;
		}
		else
			j++;
	}
	
	while ( i < Flen ) Sum += First[i++];
	
	
	return Sum;
}

Here is a O(n) solution

#include <stdio.h>
#include <conio.h>

void printSum(int arr1[],int n,int arr2[],int m)
{
	int diff1=0,diff2=0,sum1=0,sum2=0,final_sum=0,sum3=0,sum4=0,i=0,j=0;
	while(i<n&&j<m)
	{
		diff1=arr1[i]-arr2[j];
		diff2=arr2[j]-arr1[i];
		sum1=sum1+diff1;
		sum2=sum2+diff2;
		sum3=sum3+arr1[i];
		sum4=sum4+arr2[j];
		if(diff1==0&&diff2==0)
		{
			if(sum1>sum2)
			{
				final_sum+=sum3;
			}
			else
				final_sum+=sum4;
			sum3=0,sum4=0;
		}
		i++,j++;
	}
	if(m<n)
	{
		while(i<n)
		{
			sum3=sum3+arr1[i++];
		}
		final_sum+=sum3;
	}
	else if(n<m)
	{
		while(j<m)
		{
			sum4=sum4+arr2[j++];
		}
		final_sum+=sum4;
	}
	else
	{
		if(sum3>sum4)
			final_sum+=sum3;
		else
			final_sum+=sum4;	
	}
	printf("Final sum is %d",final_sum);
}
int main()
{
	int arr1[]={3,5,7,9,20,25,30,40,55,56,57,60,62};
	int arr2[]={1,4,7,11,14,25,44,47,55,57,100};
	int n=sizeof(arr1)/sizeof(arr1[0]);
	int m=sizeof(arr2)/sizeof(arr2[0]);
	printSum(arr1,n,arr2,m);	
}

My first post. It seems recursive works here. I define a func max_sum to compute the max sum beginning from index n. the func returns two max values, one for starting at first array, the other for starting at second. I print out the optimal sequence in reverse order at the first column of the output, and the sum at the second column. The last row gives the total optimal sum.

p.s. I saw others use two indices i and j for two arrays, while I use one. Can anyone show me the difference? Thanks.

#include <cstdio>
struct Res {
     int first_max;
     int second_max;
};

Res max_sum(int * first, int * second, int first_len, int second_len, int n);
int main (int argc, char * argv[])
{
     int  first_arr[] = {3, 5, 7,  9, 20, 25, 30, 40, 55, 56, 57, 60, 62}; 
     int second_arr[] = {1, 4, 7, 11, 14, 25, 44, 47, 55, 57, 100};

     max_sum(first_arr, second_arr, sizeof(first_arr)/sizeof(first_arr[0]), sizeof(second_arr)/sizeof(second_arr[0]), 0);

}

Res max_sum(int * first, int * second, int first_len, int second_len, int n)
{
     Res res, res1;
     res.first_max = 0;
     res.second_max = 0;

     // index go over first array boundary.
     if (n >= first_len && n < second_len) {
	  res1 = max_sum(first, second, first_len, second_len, n+1);
	  res.first_max = 0;
	  res.second_max = second[n] + res1.second_max;
	  printf("%i %i\n", second[n], res.second_max);
     }
     // index go over second array boundary.
     else if (n < first_len && n >= second_len) {
	  res1 = max_sum(first, second, first_len, second_len, n+1);
	  res.second_max = 0;
	  res.first_max = first[n] + res1.first_max;
	  printf("%i %i\n", first[n], res.first_max);
     }

     // index go over both array boundaries.
     else if (n >= first_len && n >= second_len) {
	  res.first_max = 0;
	  res.second_max = 0;
     }

     // index within range of both arrays.
     else {
	  // compute max sum for n+1.
	  res1 = max_sum(first, second, first_len, second_len, n+1);

	  // at intersection point.
	  if (first[n] == second[n]) {
	       res.first_max = res1.second_max;
	       res.second_max = res1.first_max;

	       if (res1.first_max > first[n] + res1.second_max) {
		    res.first_max = first[n] + res1.first_max;
	       }
	       else {
		    res.first_max = first[n] + res1.second_max;
	       }

	       if (res1.second_max > first[n] + res1.first_max) {
		    res.second_max = first[n] + res1.second_max;
	       }
	       else {
		    res.second_max = first[n] + res1.first_max;
	       }

	       if (res.first_max > res.second_max) {
		    printf("%i %i\n", first[n], res.first_max);
	       }
	       else {
		    printf("%i %i\n", second[n], res.second_max);
	       }

	  }

	  // not intersection. 
	  else {
	       res.first_max = first[n] + res1.first_max;		    
	       res.second_max = second[n] + res1.second_max;
	       if (res.first_max > res.second_max) {
		    printf("%i %i\n", first[n], res.first_max);
	       }
	       else {
		    printf("%i %i\n", second[n], res.second_max);
	       }

	  }
     }
     return res;
}

My proposal in Java.

public static int max(int a, int b){
        return a > b ? a : b;
    }
    
    private static int biggestSum(int[] first, int[] second, int n, int sum, int current) {
        if((n == first.length && current == 1) || (n == second.length && current == 2))
            return sum;
        else if(n >= first.length)
            return sum += biggestSum(first, second, n + 1, sum, 2) + second[n]; 
        else if(n >= second.length)
            return sum += biggestSum(first, second, n + 1, sum, 1) + first[n];
        
        
        if(first[n] == second[n])
            sum += max(biggestSum(first, second, n + 1, sum, 1) + first[n], biggestSum(first, second, n + 1, sum, 2) + second[n]);
        else if(current == 1)
            sum += biggestSum(first, second, n + 1, sum, 1) + first[n];
        else if(current == 2)
            sum += biggestSum(first, second, n + 1, sum, 2) + second[n];
        return sum;
    }
    
    public static void main(String [] args){
        int first[] = {3, 5, 7, 9, 20, 25, 30, 40, 55, 56, 57, 60, 62};
        int second[] = {1, 4, 7, 11, 14, 25, 44, 47, 55, 57, 100};
        int max_sum = max(biggestSum(first, second, 0, 0, 1), biggestSum(first, second, 0, 0, 2));
        System.out.println(max_sum); // 450
    }

Here is solution on D:

import std.stdio;
import std.typecons;
import std.algorithm;

int[] get_first_intersection(int[] lhs, int[] rhs)
{
	if (lhs.length == 0 || rhs.length == 0) return [];
	if (lhs[0] == rhs[0]) return [ rhs[0] ];
	return lhs[0] > rhs[0] ? get_first_intersection(lhs, rhs[1..$]) : get_first_intersection(lhs[1..$], rhs);
}

int[] select_max_path(int[] lhs, int[] rhs)
{
	alias Sum = reduce!"a + b";
	return Sum(0, lhs) > Sum(0, rhs) ? lhs : rhs;
}

int[] build_path(int[] lhs, int[] rhs)
{
	auto fi = get_first_intersection(lhs, rhs);
	if (fi.length == 0) return select_max_path(lhs, rhs);
	auto lh = findSplit(lhs, fi);
	auto rh = findSplit(rhs, fi);
	return select_max_path(lh[0] ~ lh[1], rh[0] ~ rh[1]) ~ build_path(lh[2], rh[2]);
}

unittest
{
    int[] a = [3, 5, 7, 9, 20, 25, 30, 40, 55, 56, 57, 60, 62];
	int[] b = [1, 4, 7, 11, 14, 25, 44, 47, 55, 57, 100];
	assert(get_first_intersection(a, b) == [7]);

	assert(select_max_path([3, 5, 7], [1, 4, 7]) == [3, 5, 7]);
	assert(select_max_path([1, 4, 7], [3, 5, 7]) == [3, 5, 7]);
	assert(select_max_path([3, 5, 7], [3, 5, 7]) == [3, 5, 7]);
	
	auto res = findSplit(a, [7]);
	assert(res[0] == [3, 5]);
	assert(res[1] == [7]);
	assert(res[2] == [9, 20, 25, 30, 40, 55, 56, 57, 60, 62]);

	assert(build_path(a,b) == [3, 5, 7, 9, 20, 25, 44, 47, 55, 56, 57, 60, 62]);
	assert(reduce!"a + b"(0, build_path(a,b)) == 450);
}

int main(string[] argv)
{
    int[] a = [3, 5, 7, 9, 20, 25, 30, 40, 55, 56, 57, 60, 62];
	int[] b = [1, 4, 7, 11, 14, 25, 44, 47, 55, 57, 100];
	writeln("Best Path:", build_path(a,b));
	writeln("Total Sum:", reduce!"a + b"(0, build_path(a,b)));
    return 0;
}

Output:
Best Path:[3, 5, 7, 9, 20, 25, 44, 47, 55, 56, 57, 60, 62]
Total Sum:450

int main()
{
int i=0,j=0;
int m=0,n=0;
int sum=0;
int sum_a=0,sum_b=0;
int[] a = [3, 5, 7, 9, 20, 25, 30, 40, 55, 56, 57, 60, 62];
int[] b = [1, 4, 7, 11, 14, 25, 44, 47, 55, 57, 100];

while( i<a.length && j<b.length)
{
if(a[m]!=b[n])
{
sum_a+=a[m];
sum_b+=b[n];
m++;
n++;
}

else if(a[m]==b[n])
sum= a[m]+max(sum_a,sum_b);
}


return sum;
}

I modified the codes from the first answer a little bit and this should work.

private static int max (int a, int b)
{
if (a > b)
return a;
else
return b;
}

public static void CalLargest(int [] a, int [] b)
{
int sum_subarray_a = 0;
int sum_subarray_b = 0;
int max_sum = 0;
int i = 0;
int j = 0;
int temp = 0;

while ( i < a.length - 1 && j < b.length - 1 ) {
sum_subarray_b += b[j];
j++;
sum_subarray_a += a[i];
i++;
if(a[i] == b[j]) {
max_sum += max(sum_subarray_a, sum_subarray_b);
sum_subarray_a = sum_subarray_b = 0;
temp = i;
}
}
sum_subarray_a = sum_subarray_b = 0;
for (int k = temp; k < a.length; k++)
{
sum_subarray_a += a[k];
}
for (int l = temp; l < b.length; l++)
{
sum_subarray_b += b[l];
}

max_sum += max(sum_subarray_a, sum_subarray_b);

System.out.println("Max Sum is : " + max_sum);

}

int maxSum (int* array1, int array1Size, int* array2, int array2Size){
    int sum1 = 0;
    int sum2 = 0;
    
    int* ptr1 = array1;
    int* ptr2 = array2;
    
    while ((array1Size > (ptr1 - array1)) && ((array2Size > (ptr2 - array2Size)))){
        if (*ptr1 < *ptr2){
            sum1 += *ptr1;
            ++ptr1;
        }
        
        if (*ptr1 > *ptr2){
            sum2 += *ptr2;
            ++ptr2;
        }
        
        if (*ptr1 == *ptr2){
            if (sum2 > sum1){
                sum1 = sum2;
            }
            else{
                sum2 = sum1;
            }
        }
    }
    
    while (array1Size < (ptr1 - array1)){
        sum1 += *ptr1;
        ++ptr1;
    }
    
    while (array2Size < (ptr2 - array2)){
        sum2 += *ptr2;
        ++ptr2;
    }
    
    return (sum1 > sum2) ? sum1 : sum2;

}

int maxSum (int* array1, int array1Size, int* array2, int array2Size){
    int sum1 = 0;
    int sum2 = 0;
    
    int* ptr1 = array1;
    int* ptr2 = array2;
    
    while ((array1Size > (ptr1 - array1)) && ((array2Size > (ptr2 - array2Size)))){
        if (*ptr1 < *ptr2){
            sum1 += *ptr1;
            ++ptr1;
        }
        
        if (*ptr1 > *ptr2){
            sum2 += *ptr2;
            ++ptr2;
        }
        
        if (*ptr1 == *ptr2){
            if (sum2 > sum1){
                sum1 = sum2;
            }
            else{
                sum2 = sum1;
            }
        }
    }
    
    while (array1Size < (ptr1 - array1)){
        sum1 += *ptr1;
        ++ptr1;
    }
    
    while (array2Size < (ptr2 - array2)){
        sum2 += *ptr2;
        ++ptr2;
    }
    
    return (sum1 > sum2) ? sum1 : sum2;
}

Try this Java Code:-

public static void main(String[] args)
{
int[] arr1 = new int[] { 3, 5, 7, 9, 20, 25, 30, 40, 55, 56, 57, 60, 62 };
int[] arr2 = new int[] { 1, 4, 7, 11, 14, 25, 44, 47, 55, 57, 100 };
ArrayList<Integer> sum1 = new ArrayList<Integer>();
int s = 0, mainSum = 0, intersectionsum = 0, k = 0;

for (int i = 0; i < arr1.length; i++)
{
int n1 = arr1[i];
s += n1;
for (int j = 0; j < arr2.length; j++)
{
int n2 = arr2[j];
if(n1 < n2)
break;
if(n1==n2)
{
intersectionsum+= n1;
sum1.add(s - n1);
s = 0;
}
}
}
sum1.add(s);
s = 0;
for (int i = 0; i < arr2.length; i++)
{
int n1 = arr2[i];
s += n1;
for (int j = 0; j < arr1.length; j++)
{
int n2 = arr1[j];
if(n1 < n2)
break;
if(n1==n2)
{
mainSum += (sum1.get(k)>(s - n1))?sum1.get(k):(s - n1);
++k;
s = 0;
}
}
}
mainSum += (sum1.get(k)>s)?sum1.get(k):s;
mainSum += intersectionsum;
System.out.println(mainSum);
}

Move along each path by comparing the values at each point. Increment the path with the lowest value and add the value to the path's sum.
When you reach an intersection point, compare the sums of the paths up to this point and add the largest sum to the total sum.

#include<iostream>
#include<string>
using namespace std;

int MaxSumPath(int a[], int b[], int l1, int l2)
{
	
	int i = 0;
	int j = 0;
	int totalSum = 0;
	int sumA = 0;
	int sumB = 0;
     
	while(i< l1 && j < l2)
	{
		// If points are equal ,at intersection, add biggest sum
		if(a[i] == b[j])
		{
			if(sumA > sumB)
			{
				sumA += a[i];
				totalSum += sumA;
			}
			else
			{
				sumB += b[j];
				totalSum += sumB;
			}
			sumA = 0;
			sumB = 0;
			i++;
			j++;
		}
		// Else we must move on the paths
		else
		{
			// Check which element is bigger
			// Then increment the position of the smaller value
			if(a[i] < b[j])
			{
				sumA += a[i];
				i++;
			}
			else
			{
				sumB += b[j];
				j++;
			}
		}
	}


	// Loop may finish without adding all elements in the list
	// This will occur when the last point is not one of interception
	// We therefore need to add these points to the path sums
	while(i < l1)
	{
		sumA += a[i];
		i++;
	}
	while(j < l2)
	{
		sumB += b[j];
		j++;
	}
	// Need to add the leftover sums
	if(sumA > sumB)
	{
		totalSum += sumA;
	}
	else
	{
		totalSum += sumB;
	}
	return totalSum;
	
}

int main()
{

   int arr1[] = {3, 5, 7, 9, 20, 25, 30, 40, 55, 56, 57, 60, 62}; 
   int arr2[] = {1, 4, 7, 11, 14, 25, 44, 47, 55, 57,100};
   int sum = MaxSumPath(arr1,arr2,13,11);
   cout<< "answer = " << sum << endl;
   return 0;
}

/* package whatever; // don't place package name! */
// IDEONE link ideone.com/On1CjH
import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	// Solution for question :
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		int[] a1 = {3, 5, 7, 9, 20, 25, 30, 40, 55, 56, 57, 60, 62},
		a2 = {1, 4, 7, 11, 14, 25, 44, 47, 55, 57, 100};
		int i1=0, i2=0, sum1=0, sum2=0;
		while(i1<a1.length || i2<a2.length){
			if(i1==a1.length){
				sum2 += a2[i2++];
			}else if(i2==a2.length){
				sum1 += a1[i1++];
			}else if(a1[i1]==a2[i2]){
				// reset sum as zero and record current index
				//path.push(sum1>sum2 ? (a1, i1) : (a2, i2));
				System.out.println(sum1>sum2?"Array 1, index "+i1:"Array 2, index "+i2);
				i1++; i2++;
			}else{
				// if sum1 is less, increment i1 else increment i2. Also, update corr. sum1 or sum2.
				if(sum1<sum2){
					sum1 += a1[i1];
					i1++;
				}else{
					sum2 += a2[i2];
					i2++;
				}
			}
		}
	}
}

public class TestPract0709_1 {
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		int[] firstArray = {3, 5, 7, 9, 20, 25, 30, 40, 55, 56, 57, 60, 62}; 
		int[] secondArray = {1, 4, 7, 11, 14, 25, 44, 47, 55, 57, 100};
		int iNewBegin = 0, jNewBegin = 0, iNewEnd = 0, jNewEnd = 0, sum = 0;
		
		for(int i = 0; i<firstArray.length; i++){
			for(int j = jNewBegin + 1; j<secondArray.length; j++){
				if((i == firstArray.length - 1) && (sum > 0)){
					int sumFirst = sum(firstArray, iNewBegin, firstArray.length);
					int sumSecond = sum(secondArray, jNewBegin, secondArray.length);
					sum += (sumFirst > sumSecond)? sumFirst: sumSecond;
				}
				else if(firstArray[i] == secondArray[j]){
					iNewEnd = i;
					jNewEnd = j;
					int sumFirst = sum(firstArray, iNewBegin, iNewEnd);
					int sumSecond = sum(secondArray, jNewBegin, jNewEnd);
					sum += (sumFirst > sumSecond)? sumFirst: sumSecond;
					iNewBegin = iNewEnd;
					jNewBegin = jNewEnd;
				}
				
			}
		}
		
		System.out.println("The largest possible sum is " + sum);
		
		
	}
	
	public static int sum(int[] v, int begin, int end){
		
		int sum = 0;
		for(int i = begin; i < end; i++){
			sum += v[i];
		}
		return sum;
	}
}

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int max_sum(int *A, int *B, int n, int m){

	int sum = 0;
	int sum_A = 0;
	int sum_B = 0;
	int i = 0;
	int j = 0;
	int a_i = 0;
	int b_j = 0;

	while (i<n || j<m){
		a_i = A[i];
		b_j = B[j];

		while ((a_i != b_j) && (i<n && j<m)){
			if (a_i > b_j) {
				sum_B += b_j;
				j++;	
				b_j = B[j];
				
			}
			else {
				sum_A += a_i;
				i++;
				a_i = A[i];
			}
		}
		
		
		if (a_i == b_j) {
			sum_A += a_i;
			sum_B += b_j;
			//printf ("a_i = b_j = %d sum_A = %d, sum_B = %d ", a_i, sum_A, sum_B); 
			sum += (sum_A > sum_B ? sum_A : sum_B);
			sum_A = 0;
			sum_B = 0;
			i++;
			j++;
			//printf ("Sum = %d\n", sum);
		}
		else{			
			//printf ("i = %d a_i = %d j = %d b_j = %d sum_A = %d, sum_B = %d\n", i, a_i, j, b_j, sum_A, sum_B); 
			while (i<n){
				sum_A += A[i];
				i++;				
			}	
			while (j<m){
				sum_B += B[j];
				j++;
			}
			//printf ("i = %d a_i = %d j = %d b_j = %d sum_A = %d, sum_B = %d\n", i, a_i, j, b_j, sum_A, sum_B);
			sum += (sum_A > sum_B ? sum_A : sum_B);
			break;
		}
	}
	return sum;
}

int main(){

	int A[] = {3, 5, 7, 9, 20, 25, 30, 40, 55, 56, 57, 60, 62}; 
	int n = sizeof(A)/sizeof(int);
	int B[] = {1, 4, 7, 11, 14, 25, 44, 47, 55, 57, 100};
	int m = sizeof(B)/sizeof(int);
	printf("Max sum is %d\n", max_sum(A, B, n, m));
	return 0;
}

public static int getMax(int[] s1, int[] s2, int counter, ref string route)
{
if (counter > s1.Length - 1) return 0;
route += ", " + s1[counter].ToString();
if (counter == s1.Length - 1) return s1[counter];

//Console.WriteLine(", " + s1[counter].ToString());
string r1 = route;
string r2 = route;
var sum1 = s1[counter] + getMax(s1, s2, counter + 1, ref r1);
int sum2 = 0;
if (counter <= s2.Length - 1 && s1[counter] == s2[counter]) {
sum2 = s1[counter] + getMax(s2, s1, counter + 1,ref r2);

//Console.WriteLine((sum1 > sum2)? r1: r2);
//Console.WriteLine((sum1 > sum2)? sum1: sum2);
}
return (sum1 > sum2)? sum1 : sum2;
}

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;
int getSum(const vector<int> &a, const vector<int> &b){
    int max_sum = 0;
    unordered_set<int> a_hash;
    vector<int> common;
    common.reserve(max(a.size(), b.size()));
    // find the common elements.
    for(auto &i: a){
        a_hash.insert(i);
    }
    for(auto &i: b){
        if(a_hash.find(i) != a_hash.end()) common.push_back(i);
    }
    
    unsigned i=0, j=0;
    int sum_a =0, sum_b =0;
    bool done = false;
    for(auto it= common.begin(); !done; ++it){
        sum_a =0; sum_b =0;
        if (it == common.end()) { done=true; } // still need to proceed(just once) to add elements beyond the last common point.
        for(;i<a.size();++i){
            if (!done && a[i] == *it) break;
            sum_a += a[i];
        }
        for(;j<b.size();++j){
            if (!done && b[j] == *it) break;
            sum_b += b[j];
        }
        max_sum += std::max(sum_a, sum_b) + *it;
        ++i; ++j; // move past the common element
    }
    return max_sum;
}

int main() {

    vector<int> a = {3, 5, 7, 9, 20, 25, 30, 40, 55, 56, 57, 60, 62};
    vector<int> b = {1, 4, 7, 11, 14, 25, 44, 47, 55, 57, 100};
    cout << getSum(a,b)<< "\n";
    vector<int> ret;
    cout << "Done!\n";
    return 0;
}

def greatSum(first, second):
    return max(greatSumRec(first, second), greatSumRec(second,first))
    

def greatSumRec(l1, l2):
    if l1 == [] or l2 == []:
        return []
    if l1[0] == l2[0]:
        print 'l1', l1
        print 'l2', l2
        return [l1[0]]+max(greatSumRec(l1[1:],l2[1:]),greatSumRec(l2[1:],l1[1:]), key=sum)
    else:
        print 'l1', l1
        print 'l2', l2
        return [l1[0]]+greatSumRec(l1[1:], l2[1:])

public static int sol2(int[] arr1, int[] arr2)
{
Map<Integer,Integer> map = new HashMap<Integer, Integer>();
int temp = 0;
for(int i : arr1)
{
temp+=i;
map.put(i,temp); //max values with respect to 0
}
int totalsum = 0;
temp = 0; int prevIntersectionVal = 0;
for(int i : arr2)
{
temp+=i;
Integer val = map.get(i);
if(val != null)
{
int ins1 = val - prevIntersectionVal;
prevIntersectionVal = val;
if(temp > ins1)
totalsum+=temp;
else
totalsum+=ins1;
temp = 0;
}
}
int lastSum = map.get(arr1[arr1.length-1]) - prevIntersectionVal;
totalsum+= lastSum > temp ? lastSum : temp;
return totalsum;
}

//java
public class Adobesde12 {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        Scanner in = new Scanner(System.in);
        int i,n,m;
        n=in.nextInt();
        m=in.nextInt();
        int[] a=new int[n];
        int[] b=new int[m];
        ArrayList<Integer> set=new ArrayList<Integer>();
        ArrayList<Integer> set1=new ArrayList<Integer>();
        for(i=0;i<n;i++)
        {
            a[i]=in.nextInt();
            set.add(a[i]);
        }
        for(i=0;i<m;i++)
        {
            b[i]=in.nextInt();
            set1.add(b[i]);
        }
        int j=0;
        i=0;
        int sum=0,sum1=0,maxsum=0;
        while(i<n && j<m )
        {
            if(set1.contains(a[i])&& set.contains(b[j]))
            {
                maxsum+=Math.max(sum,sum1);
                maxsum+=a[i];
                i++;
                j++;
                sum=0;
                sum1=0;
            }
            if(!set1.contains(a[i]))
            {
                sum+=a[i];
                i++;
            }
            if(!set.contains(b[j]))
            {
                sum1+=b[j];
                j++;
            }
        }
        while(i<n)
        {
            sum+=a[i++];
        }
        while(j<m)
        {
            sum1=b[j++];
        }
        maxsum+=Math.max(sum,sum1);
        
        System.out.println(maxsum);
       
    }
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class DoubleHelix {
    public static void main(String[] str) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String st = in.readLine();
       // Scanner in = new Scanner(System.in);
      //  int n1 = in.nextInt();
        String[] s1 = st.split(" ");
        int n1 = Integer.parseInt(s1[0]);
        while(!st.equals("0")) {
            int[] arr1 = new int[n1];
            for (int i = 0; i < n1; i++)
                arr1[i]=Integer.parseInt(s1[i+1]);
                //arr1[i] = in.nextInt();
            String st1 = in.readLine();
            String[] s2 = st1.split(" ");
           // int n2 = in.nextInt();
            int n2 = Integer.parseInt(s2[0]);
           // System.out.println("seq:" + n1 + " " + n2);
            int[] arr2 = new int[n2];
            for (int i = 0; i < n2; i++)
                arr2[i]=Integer.parseInt(s2[i+1]);
               // arr2[i] = in.nextInt();

                int m=0,n=0,sum1=0,sum2=0,fsum=0;
            while(m<n1 && n<n2) {
                if (arr1[m] < arr2[n]) {
                    while (m<n1 && arr1[m] < arr2[n]) {
                       // System.out.println("sum1:" + sum1);
                            sum1 += arr1[m];
                       // System.out.println("sum1:" + sum1+" coz:"+arr1[m]);
                        m++;
                    }
                }
                else if(arr1[m] > arr2[n]) {
                    while (n<n2 && arr1[m] > arr2[n]) {
                       // System.out.println("sum2:"+sum2);
                            sum2 += arr2[n];
                       // System.out.println("sum2:"+sum2+" coz:"+arr2[n]);
                        n++;
                    }
                }
                else
                {
                    fsum =fsum+((sum1>sum2)? sum1 : sum2);
                    fsum = fsum+arr1[m];
                    sum1=0; sum2=0;
                  //  System.out.println("sum:"+fsum+" till "+arr1[m]);
                    m++;n++;

                }
            }

            if(m==n1)
            {
                while(n<n2) { //System.out.println("1");
                    sum2 += arr2[n++];
                }

            }
            else if(n==n2)
            {
                while(m<n1) { //System.out.println("2");
                    sum1 += arr1[m++];
                }
            }

            fsum+=(sum1>sum2)?sum1:sum2;

            System.out.println(fsum);

            //n1 = in.nextInt();
             st = in.readLine();
            s1 = st.split(" ");
             n1 = Integer.parseInt(s1[0]);

        }



    }
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class DoibleHelix {
    public static void main(String[] str) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String st = in.readLine();
       // Scanner in = new Scanner(System.in);
      //  int n1 = in.nextInt();
        String[] s1 = st.split(" ");
        int n1 = Integer.parseInt(s1[0]);
        while(!st.equals("0")) {
            int[] arr1 = new int[n1];
            for (int i = 0; i < n1; i++)
                arr1[i]=Integer.parseInt(s1[i+1]);
                //arr1[i] = in.nextInt();
            String st1 = in.readLine();
            String[] s2 = st1.split(" ");
           // int n2 = in.nextInt();
            int n2 = Integer.parseInt(s2[0]);
           // System.out.println("seq:" + n1 + " " + n2);
            int[] arr2 = new int[n2];
            for (int i = 0; i < n2; i++)
                arr2[i]=Integer.parseInt(s2[i+1]);
               // arr2[i] = in.nextInt();

                int m=0,n=0,sum1=0,sum2=0,fsum=0;
            while(m<n1 && n<n2) {
                if (arr1[m] < arr2[n]) {
                    while (m<n1 && arr1[m] < arr2[n]) {
                       // System.out.println("sum1:" + sum1);
                            sum1 += arr1[m];
                       // System.out.println("sum1:" + sum1+" coz:"+arr1[m]);
                        m++;
                    }
                }
                else if(arr1[m] > arr2[n]) {
                    while (n<n2 && arr1[m] > arr2[n]) {
                       // System.out.println("sum2:"+sum2);
                            sum2 += arr2[n];
                       // System.out.println("sum2:"+sum2+" coz:"+arr2[n]);
                        n++;
                    }
                }
                else
                {
                    fsum =fsum+((sum1>sum2)? sum1 : sum2);
                    fsum = fsum+arr1[m];
                    sum1=0; sum2=0;
                  //  System.out.println("sum:"+fsum+" till "+arr1[m]);
                    m++;n++;

                }
            }

            if(m==n1)
            {
                while(n<n2) { //System.out.println("1");
                    sum2 += arr2[n++];
                }

            }
            else if(n==n2)
            {
                while(m<n1) { //System.out.println("2");
                    sum1 += arr1[m++];
                }
            }

            fsum+=(sum1>sum2)?sum1:sum2;

            System.out.println(fsum);

            //n1 = in.nextInt();
             st = in.readLine();
            s1 = st.split(" ");
             n1 = Integer.parseInt(s1[0]);

        }



    }
}

public class TwoArraysPathWithMaximumdata {

public static void main(String[] args) {

//int[] arr1 = { 3, 5, 7, 9, 20, 25, 30, 40, 55, 56, 57, 60, 62 };
//int[] arr2 = { 1, 4, 7, 11, 14, 25, 44, 47, 55, 57, 100 };

int[] arr1 = { 3, 5, 7, 9, 20, 25, 30, 40, 55, 56, 57,100 };
int[] arr2 = { 1, 4, 7, 11, 14, 25, 44, 47, 55, 57,60, 62 };

System.out.println("Maximum sum is " + MaximumPathSum(arr1, arr2));
}

/**
1)Here I used the logic of merge sort if/esle , where I will check
* which array has smaller number then add it to its own sum and
* increment that particular array(other array is no incremented).
2)Now next time again check next number from teh smaller element
*array(as it got incremented last time) against the same number
* from other array and again do the above logic.
3)This way I will be able to reach the intersection point and
*also keep the sums form both arrays till that time.Now I can
*decide which sum is bigger and then use it.**/
public static int MaximumPathSum(int[] arr1, int[] arr2) {
int maxsum = 0;
int sum = 0;
int sum1 = 0;
int sum2 = 0;
int arrayindex1 = 0;
int arrayindex2 = 0;
int arr1length = arr1.length;
int arr2length = arr2.length;
StringBuilder path = new StringBuilder();
StringBuilder path1 = new StringBuilder();
StringBuilder path2 = new StringBuilder();
while (arrayindex1 < arr1length && arrayindex2 < arr2length) {

if (arr1[arrayindex1] < arr2[arrayindex2]) {
sum1 = sum1 + arr1[arrayindex1];
path1.append(arr1[arrayindex1] + ",");
arrayindex1++;
} else if (arr1[arrayindex1] > arr2[arrayindex2]) {
sum2 = sum2 + arr2[arrayindex2];
path2.append(arr2[arrayindex2] + ",");
arrayindex2++;
} else {

sum1 = sum1 + arr1[arrayindex1];
sum2 = sum2 + arr2[arrayindex2];
path1.append(arr1[arrayindex1] + ",");
path2.append(arr2[arrayindex2] + ",");
// int sum=sum1>=sum2?sum1:sum2;
if (sum1 >= sum2) {
sum = sum1;
path.append(path1);
} else {
sum = sum2;
path.append(path2);
}
maxsum = maxsum + sum;
sum1 = 0;
sum2 = 0;
path1.setLength(0);
path2.setLength(0);
arrayindex1++;
arrayindex2++;
}
}

while (arrayindex1 < arr1length) {
path1.append(arr1[arrayindex1] + ",");
sum1 = sum1 + arr1[arrayindex1++];
}
while (arrayindex2 < arr2length) {
path2.append(arr2[arrayindex2] + ",");
sum2 = sum2 + arr2[arrayindex2++];
}

if (sum1 >= sum2) {
sum = sum1;
path.append(path1);
} else {
sum = sum2;
path.append(path2);
}
maxsum = maxsum + sum;
System.out.println(path);
return maxsum;
}

}

public class TwoArraysPathWithMaximumdata {

	public static void main(String[] args) {

		//int[] arr1 = { 3, 5, 7, 9, 20, 25, 30, 40, 55, 56, 57, 60, 62 };
		//int[] arr2 = { 1, 4, 7, 11, 14, 25, 44, 47, 55, 57, 100 };
		
		int[] arr1 = { 3, 5, 7, 9, 20, 25, 30, 40, 55, 56, 57,100  };
		int[] arr2 = { 1, 4, 7, 11, 14, 25, 44, 47, 55, 57,60, 62  };

		System.out.println("Maximum sum is " + MaximumPathSum(arr1, arr2));
	}

	/** 
	 1)Here I used the logic of merge sort if/esle , where I will check 
	 * which array has smaller number then add it to its own sum and 
	 * increment that particular array(other array is no incremented). 
	 2)Now next time again check next number from teh smaller element 
	 *array(as it got incremented last time) against the same number
	 * from other array and again do the above logic.
	 3)This way I will be able to reach the intersection point and 
	 *also keep the sums form both arrays till that time.Now I can 
	 *decide which sum is bigger and then use it.**/
	public static int MaximumPathSum(int[] arr1, int[] arr2) {
		int maxsum = 0;
		int sum = 0;
		int sum1 = 0;
		int sum2 = 0;
		int arrayindex1 = 0;
		int arrayindex2 = 0;
		int arr1length = arr1.length;
		int arr2length = arr2.length;
		StringBuilder path = new StringBuilder();
		StringBuilder path1 = new StringBuilder();
		StringBuilder path2 = new StringBuilder();
		while (arrayindex1 < arr1length && arrayindex2 < arr2length) {

			if (arr1[arrayindex1] < arr2[arrayindex2]) {
				sum1 = sum1 + arr1[arrayindex1];
				path1.append(arr1[arrayindex1] + ",");
				arrayindex1++;
			} else if (arr1[arrayindex1] > arr2[arrayindex2]) {
				sum2 = sum2 + arr2[arrayindex2];
				path2.append(arr2[arrayindex2] + ",");
				arrayindex2++;
			} else {

				sum1 = sum1 + arr1[arrayindex1];
				sum2 = sum2 + arr2[arrayindex2];
				path1.append(arr1[arrayindex1] + ",");
				path2.append(arr2[arrayindex2] + ",");
				// int sum=sum1>=sum2?sum1:sum2;
				if (sum1 >= sum2) {
					sum = sum1;
					path.append(path1);
				} else {
					sum = sum2;
					path.append(path2);
				}
				maxsum = maxsum + sum;
				sum1 = 0;
				sum2 = 0;
				path1.setLength(0);
				path2.setLength(0);
				arrayindex1++;
				arrayindex2++;
			}
		}

		while (arrayindex1 < arr1length) {
			path1.append(arr1[arrayindex1] + ",");
			sum1 = sum1 + arr1[arrayindex1++];
		}
		while (arrayindex2 < arr2length) {
			path2.append(arr2[arrayindex2] + ",");
			sum2 = sum2 + arr2[arrayindex2++];
		}

		if (sum1 >= sum2) {
			sum = sum1;
			path.append(path1);
		} else {
			sum = sum2;
			path.append(path2);
		}
		maxsum = maxsum + sum;
		System.out.println(path);
		return maxsum;
	}
	
}

// using merge sort algorithm.
#include <stdio.h>
void printpath( int a[], int start, int end){
     
     while( start <=end)  printf("%d\t",a[start++]);
     
     }
void findmaxpath( int a[], int b[],int i, int j,int N,int M){
     int sumA=0,sumB=0,io=i,jo=j,chk;
     while(1){
              if( a[i] > b[j]){
                  sumB= sumB+b[j];
                  j++;
                  }
              else if (a[i] < b[j]){
                  sumA= sumA+a[i];
                  i++;
                  }
              if(a[i]==b[j]){
                             if( sumA > sumB)printpath(a,io,i);
                             else  printpath(b,jo,j);
                            
                             break;
                             }
              if(i == N-1 || j==M-1) break;
                             }
     if((i==N-1 && j !=M-1)|| (i!=N-1 && j ==M-1)) {
                sumA=sumB=0;
                for(i=io;i<N;i++) { sumA=sumA+a[i];}
                for(i=jo;i <M;i++) { sumB=sumB+b[i];}
                if( sumA > sumB)printpath(a,io,N-1);
                else  printpath(b,jo,M-1);
                return;
                }
     
     else if ( i==N-1 && j ==M-1){
             sumA=sumA+a[N-1];
             sumB=sumB+b[M-1];
             if( sumA > sumB)printpath(a,io,i);
             else  printpath(b,jo,j);
            
          }
     else { findmaxpath(a,b,i+1,j+1,N,M);}
     }
main()
{
      int a[]={3,5,7,9,20,25,30,40,55,56,57,60,62,100,890};
      int b[]={1,4,7,11,14,25,44,47,55,57,100,200};
      int lena, lenb,i,j;
      int sumA=0,sumB=0,io=0,jo=0;
      lena=sizeof(a)/sizeof(a[0]);
      lenb=sizeof(b)/sizeof(b[0]);
      findmaxpath(a,b,0,0,lena,lenb);
      scanf("%d",&i);
      }

@redM0nk: this does not work because a and b are advancing at the same pace, but the intersection could happen somewhere eles in the arrays. for example index 10 could be equal to index 20 of the other array!!!

Need a little clarification:
How can we know that a particular element is an Intersection point ??
Is there any rule like every 3th element is an intersection point??
Or do we have to find out manually??