Maximum Sum Path

Vibhor Bhatnagar
Last Updated: May 13, 2022

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. 

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 both the 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).

Frequently asked questions

Q1. What is space complexity?

Ans. The space complexity of an algorithm is the overall space taken by algorithm w.r.t input size.

 

Q2. What is time complexity?

Ans. The time complexity of an algorithm can be defined as the time taken by the computer to run an algorithm.

 

Q3. What is sorting?

Ans. Sorting refers to the arrangement of data in a particular order be it ascending order or descending order.

Key takeaways

In this article, we discussed the problem of finding the maximum sum path and its most efficient approach. We hope you have gained a better understanding of the solution to this problem and, now it is your responsibility to solve the problem and try some new and different approaches to this problem. 

Until then, Keep Learning and Keep Coding and practicing on Code studio.

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think