Maximum Sum Path

Introduction

This blog will discuss the solution to the problem find the maximum sum path. We are given two arrays. We can modify the two arrays(change the order of elements in the array as we wish) and find the maximum sum path. The maximum sum path of two arrays, A and B, can be defined as follows: We start from the beginning of either of the arrays and add the elements to our sum. We can switch to another array if we reach the indexes where both the arrays have the same elements and when we reach the last index of either of the array, either we switch to the other array if possible, or else we print the sum. From all such possible sums obtained through different paths via switching, we need to find the maximum possible sum. So before we deep dive into the solution to this problem, we should first look at some examples to better understand the problem.

Sample Examples

Input: 

5 4 

8 9 1 2 5

5 4 3 7

Output: 

29 

Explanation:

The maximum  sum path will be 3 + 4 + 5 + 8 + 9 = 29. 

Input: 

3 3 

4 5 6

1 2 3

Output: 

15

Explanation:

The maximum  sum path will be 4 + 5 + 6= 15. 

Also read, Euclid GCD Algorithm

Approach

To solve this problem, we will first sort both the arrays, and after that, we will maintain two variables, one for the sum from the first array and the other for the sum from the second array, and whenever we find two identical elements, then we will add the larger sum of two arrays and after that we will run a while loop till both the elements of the arrays are equal. We will repeat this process till the array ends.

Algorithm

1. Firstly we will sort both the arrays using the inbuilt sort function of C++. To read more about sorting, please refer to this blog.
2. After that, we will take two variables, sumA, and sumB, to store the sums of both arrays. We will add all elements of array A in sumA and array B in sumB. We will do this until there is an equal element.
3. When we find an element in both the arrays, we will store the maximum of both these sums, and we will traverse another while loop until the elements are equal in both the arrays.
4. We will repeat this process until the first array is finished, the second array is finished, or both the arrays are finished.

Implementation in C++

// C++ implementation to find maximum sum path
#include <bits/stdc++.h>
using namespace std;

int main()
{
    // to store the size of both the arrays
    int n1, n2;
    cin >> n1 >> n2;
    int a[n1], b[n2];
    for (int i = 0; i < n1; i++)
    {
        cin >> a[i];
    }
    for (int i = 0; i < n2; i++)
    {
        cin >> b[i];
    }
    // sorting first array using inbuilt sort function of c++
    sort(a, a + n1);

    // sorting second array using inbuilt sort function of c++
    sort(b, b + n2);

    // to store the index values of both the arrays
    int i = 0, j = 0;

    // to store the individual sum of both the arrays
    // untill there is a common element in both the arrays
    int sumA = 0, sumB = 0;

    // to store the final answer
    int finalSum = 0;

    while (i < n1 && j < n2)
    {
        // if (a[i] < b[j]) then add this element 
        // in sumA and increment the value of i
        if (a[i] < b[j])
        {
            sumA += a[i++];
        }
        // if (b[j] < a[i]) then add this element 
        // in sumB and increment the value of j        
        else if (b[j] < a[i])
        {
            sumB += b[j++];
        }
        else
        {
            // taking max of both the sums and
            // storing it in the final answer
            finalSum += max(sumA, sumB);

            // reintializing both values to zero
            sumA = sumB = 0;

            // traversing in both the arrays till they have same elements
            while (a[i] == b[j] && i < n1 && j < n2)
            {
                finalSum += a[i];
                // incrementing both the indexes simultaneously
                i++;j++;
            }
        }
    }
    
    // to handle the edge case where the j=n2 and i is still less than n1
    while (i < n1)
    {
        sumA += a[i++];
    }

    // to handle the edge case where the i=n1 and j is still less than n2
    while (j < n2)
    {
        sumB += b[j++];
    }

    finalSum += max(sumA, sumB);
    // print the maximum sum path
    cout << "The maximum sum is: " << finalSum << endl;
}

Output:

Input: 3 3 
       4 5 6
       1 2 3
Output: The maximum sum is: 15 

Complexity Analysis

Time Complexity: O(N(log(N)))

Since we are sorting both the arrays and traversing them, therefore, the time complexity will be equal to O(N + N(log(N))) which is approximately equal to O(N(log(N))).

Space Complexity: O(1)

Since we are not using any extra array, the space complexity will be O(1).