Double Helix Problem – Dynamic Programming Solutions

This is a C++ Program that Solves Double Helix Problem using Dynamic Programming technique.

Problem Description

Two finite, strictly increasing, integer sequences are given. Any common integer between the two sequences constitute an intersection point.

You can ‘walk” over these two sequences in the following way:
1. You may start at the beginning of any of the two sequences. Now start moving forward.
2. At each intersection point, you have the choice of either continuing with the same sequence you’re currently on, or switching to the other sequence.

The objective is finding a path that produces the maximum sum of data you walked over.

Problem Solution

We will maintain three variables result, result1 and result2. Result1 is the maximum amount of data you walked over till now currently being on sequence 1. Result2 is the maximum amount of data you walked over till now currently being on sequence 2. The final result is stored in variable result by which is the maximum of result1 and result2.

Expected Input and Output

Case-1:

advertisement
advertisement
 
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
 
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
Program/Source Code

Here is source code of the C++ Program to Solve Double Helix Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1.  
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5. int main()
  6. {
  7.  
  8.     int i,j,k;
  9.     int x,y,z;
  10.     int n1,n2;
  11.     int result1,result2,result;
  12.  
  13.     cout<<"Enter the number of elements in the first sequence ";
  14.     cin>>n1;
  15.  
  16.     result=result1=result2=0;
  17.  
  18.     vector<int> a(n1);
  19.     cout<<"Enter the values of the first sequence"<<endl;
  20.     for(i=0;i<n1;i++)
  21.     {
  22.         cin>>a[i];
  23.     }
  24.  
  25.     j=0;
  26.  
  27.     cout<<"Enter the number of elements in the second sequence ";
  28.     cin>>n2;
  29.     vector<int> b(n2);
  30.  
  31.     cout<<"Enter the values of the second sequence"<<endl;
  32.     for(i=0;i<n2;i++)
  33.     {
  34.        cin>>b[i]; 
  35.        result2+=b[i];
  36.  
  37.        while(j<n1 && a[j]<b[i])
  38.        {
  39.            result1+=a[j];
  40.            j++;
  41.        }
  42.  
  43.        if(j<n1 && a[j]==b[i])
  44.        {
  45.             result1+=a[j];
  46.             result+=max(result1,result2);     
  47.  
  48.             //reset
  49.             result1=0;
  50.             result2=0;
  51.             j++;
  52.        }
  53.     }
  54.  
  55.  
  56.     while(j<n1)
  57.     {
  58.         result1+=a[j];
  59.         j++;
  60.     }
  61.  
  62.     result+=max(result1,result2);     
  63.  
  64.     cout<<"The maximum sum of data obtained by walking over them is "<<endl;
  65.     cout<<result<<endl;
  66.  
  67.     return 0;
  68. }
Program Explanation

In the main function, we take input for elments in 2 sequences and store then in array a and b. Then after processing all these values, we display the result on the standard output.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
Runtime Test Cases
 
Case-1:
$ g++ double_helix.cpp
$ ./a.out
Enter the number of elements in the first sequence 13
Enter the values of the first sequence
3 5 7 9 20 25 30 40 55 56 57 60 62
Enter the number of elements in the second sequence 11
Enter the values of the second sequence
1 4 7 11 14 25 44 47 55 57 100
The maximum sum of data obtained by walking over them is 
450

Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.

advertisement

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.