Maximum Sum Helix path (using C++ program)

belongs to collection: Data Structure programs using C and C++ (Sorting Programs)

mahmoud2506

Save to bookmark

2022-05-08

404

Example:

Input:
A1[] = 1 2 7 11 14 25 
A2[] = 1 4 7  9 12 25 30

Output : The largest possible sum = 92

Idea: We will maintain three variables path1, path2 and pathsum. At any instant, path1 is the maximum sum of data we walked over till now, being on sequence 1. path2 is the maximum amount of data we walked over till now, being on sequence 2. The final result is stored in variable pathsum by which is the maximum of path1 and path2.

C++ programming, exam questions, C++ programming exam-questions,

All Answers

mahmoud2506

2022-05-08

need an explanation for this answer? contact us directly to get an explanation for this answer

C++ program to find maxsum of double helix

#include<bits/stdc++.h>
using namespace std;

// function for calculation of largest sum
int maxSumDHelix(int A1[], int A2[], int n1, int n2)
{
  int i, j = 0, path1 = 0, path2 = 0, pathsum = 0;

    // n1, n2 are length of both sequences
    for(i=0; i<n2; i++)
    {
       // add elements to path2
       path2 += A2[i];

       // add elements to pat1
       while(j<n1 && A1[j] < A2[i])
       {
           path1 += A1[j];
           j++;
       }

       // at intersection point update
       // path1 path2 and pathsum
       if(j<n1 && A1[j]==A2[i])
       {
            path1 += A1[j];
            pathsum += max(path1, path2);

            //reset
            path1 = 0;
            path2 = 0;
            j++;
       }
    }

    // if n1 &amp;gt; n2
    while(j<n1)
    {
        path1 += A1[j];
        j++;
    }
    // final result
    pathsum += max(path1, path2);
    return pathsum;
}


// driver program
int main()
{
    int n1,n2;
    cout<<"Enter size of 1st array :";
    cin>>n1;
    int A1[n1];
    cout<<"\nEnter elements of 1st array:\n";
    for(int i=0;i<n1;i++)
        cin>>A1[i];
    cout<<"Enter size of 2nd array:";
    cin>>n2;
    int A2[n2];
    cout<<"\nEnter elements of 2nd array:\n";
    for(int i=0;i<n2;i++)
        cin>>A2[i];
    cout << "The largest possible sum = " << maxSumDHelix(A1, A2, n1, n2);
    return 0;
}

Output

Enter size of 1st array :6

Enter elements of 1st array:
1 2 7 11 14 25
Enter size of 2nd array:7 

Enter elements of 2nd array:
1 4 7 9 12 25 30
The largest possible sum = 92

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)