Maximum sum from two sorted arrays

Question

You are given two sorted integer arrays, which have some common integers. Any common integer between the two sequences constitute an intersection point. You can start traversing from any of the array and switch to the other array or continue with the same array at an intersection point. The objective is to find a path that produces the maximum sum of the data. Take for example the following two sequences where intersection points are printed in bold: First = 3 5 7 9 20 25 30 40 55 56 57 60 62 Second = 1 4 7 11 14 25 44 47 55 57 100

In the above example, the largest possible sum is 450 which is the result of adding 3, 5, 7, 9, 20, 25, 44, 47, 55, 56, 57, 60, and 62

I wrote the following code but it is not compiling, please help:

/* M: size of the array a
   N: size of the array b
*/


int i,j,sum1,sum2,sum,m_i,n_j = 0;

void printIntersectionElements(int *a,int M, int *b, int N) {

    if (M == 0)
        return (b);
    if (N ==0)
        return(a);
    while( i < M &&  j < N ){
        sum1 = sum1 +a[i];
        sum2 = sum2 + b[j];
        if(a[i] == b[j]) { // found a common element.

            if(sum1>= sum2){
                for(;m_i<= i; m_i++)
                cout<< a[m_i];
                sum = sum +sum1; 
                m_i = i+1;
            }
            else {
                for(;n_j<= j; n_j++)
                cout<< b[n_j];
                sum = sum+sum2; 
                n_j = j+1;
            }
            sum1 = sum2 = 0;
        }
        i++;
        j++;
    }

}

Answer 1

This question can be solved in O(m+n). You can maintain a cumulative sum array for both arrays. First find the intersection point in O(m+n). Then check which array has maximum sum between two intersection point. Add them in a variable. Here is the code.

#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;

void print(int a[], int x, int y) {
    for(int i = x; i <= y; i++) {
        printf("%d ", a[i]);
    }
}

int main ()
{
    int i, j, x, y, n, m;
    int a0[100], a1[100], sum1[100], sum0[100];
    vector <int> v0, v1;
    cout << "Enter the value of n and m:\n";
    cin >> n >> m;
    scanf("%d", &a0[0]);
    sum0[0] = a0[0];
    for(i = 1; i < n; i++) {
        scanf("%d", &a0[i]);
        sum0[i] = a0[i] + sum0[i-1];    //cumulative sum for first array
    }
    scanf("%d", &a1[0]);
    sum1[0] = a1[0];
    for(i = 1; i < m; i++) {
        scanf("%d", &a1[i]);
        sum1[i] += a1[i] + sum1[i-1];   //cumulative sum for second array
    }
    i = 0;
    j = 0;
    while(i < n && j < m) {    //loop breaks when either one of the array ends
        if(a0[i] == a1[j]) {   //if there is a intersection
            v0.push_back(i);   //store index of both the arrays
            v1.push_back(j);
            i++;
            j++;
        }
        else if(a0[i] > a1[j]) {   //else increase the index of array 
            j++;                   //containing small number
        }
        else if(a0[i] < a1[j]) {
            i++;
        }
    }
    i = 0;
    j = 0;
    int sum = 0;
    while(i < v0.size()) {
        x = v0[i];
        y = v1[i];
        if(i == 0) {
            if(sum0[x] > sum1[y]) { //check which array has greater sum
                sum += sum0[x];     //first intersection
                print(a0, 0, x);
            }
            else {
                sum += sum1[y];
                print(a1, 0, y);
            }
            i++;
        }
        else {
            if(sum0[x]-sum0[v0[i-1]] > sum1[y]-sum1[v1[i-1]]) {
                sum += sum0[x]-sum0[v0[i-1]]; //checks which array has greater sum
                print(a0, v0[i-1]+1, x);      //between two intersectio
            }
            else {
                sum += sum1[y]-sum1[v1[i-1]];
                print(a1, v1[i-1]+1, y);
            }
            i++;
        }
    }
    if(sum0[n-1]-sum0[x] > sum1[m-1]-sum1[y]) {
        sum += sum0[n-1]-sum0[x];   //check which array has greater sum
        print(a0, x+1, n-1);        //at last intersection
    }
    else {
        sum += sum1[m-1]-sum1[y];
        print(a1, y+1, m-1);
    }
    cout << endl << "sum = " << sum << endl;
    return 0;
}

Answer 2

Your code has several problems:

First of it doesn't compile, since your function is declared to return void, but you try to return int*. Change your return statements to return;

However even if you fix that your function doesn't solve the problem you have described.

• Your summation stops when you reach the end of the smaller of the two arrays. However from your example you should actually go till the end of both arrays.
• Furthermore you only detect intersection points when both arrays contain the same number at the same position, however from your text I would think that you should detect points as intersections, even if they are at different positions in the array (I might be wrong though, depending on the exact formulation of your exercise). To do that the easiest way would be to handle only the smaller value of a[i] and b[j] each iteration (and increase only either i or j (or both if its an intersection).

Answer 3

You are trying to return a result from a function that is declared with a void return type. That's not valid C++, which is why you are getting a compiler error.

There may be other errors, too. Read the error messages: they will tell you exactly what and where the problem is.