Double Helix Problem - Dynamic Programming Solutions

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

Problem Description

Two ﬁnite, 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 ﬁnding 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:

 
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.

```
 
```
```
#include<bits/stdc++.h>
```
```
using namespace std;
```
```
 
```
```
int main()
```
```
{
```
```
 
```
```
    int i,j,k;
```
```
    int x,y,z;
```
```
    int n1,n2;
```
```
    int result1,result2,result;
```
```
 
```

    cout<<"Enter the number of elements in the first sequence ";

```
    cin>>n1;
```
```
 
```
```
    result=result1=result2=0;
```
```
 
```
```
    vector<int> a(n1);
```

    cout<<"Enter the values of the first sequence"<<endl;

```
    for(i=0;i<n1;i++)
```
```
    {
```
```
        cin>>a[i];
```
```
    }
```
```
 
```
```
    j=0;
```
```
 
```

    cout<<"Enter the number of elements in the second sequence ";

```
    cin>>n2;
```
```
    vector<int> b(n2);
```
```
 
```

    cout<<"Enter the values of the second sequence"<<endl;

```
    for(i=0;i<n2;i++)
```
```
    {
```
```
       cin>>b[i]; 
```
```
       result2+=b[i];
```
```
 
```
```
       while(j<n1 && a[j]<b[i])
```
```
       {
```
```
           result1+=a[j];
```
```
           j++;
```
```
       }
```
```
 
```
```
       if(j<n1 && a[j]==b[i])
```
```
       {
```
```
            result1+=a[j];
```

            result+=max(result1,result2);

```
 
```
```
            //reset
```
```
            result1=0;
```
```
            result2=0;
```
```
            j++;
```
```
       }
```
```
    }
```
```
 
```
```
 
```
```
    while(j<n1)
```
```
    {
```
```
        result1+=a[j];
```
```
        j++;
```
```
    }
```
```
 
```
```
    result+=max(result1,result2);     
```
```
 
```

    cout<<"The maximum sum of data obtained by walking over them is "<<endl;

```
    cout<<result<<endl;
```
```
 
```
```
    return 0;
```
```
}
```

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.

« Prev - Alice Kindergarten Candies Problem using Dynamic Programming

» Next - Mixtures Problem using Dynamic Programming

Related Posts:

Practice Design & Analysis of Algorithms MCQ
Apply for Computer Science Internship
Practice Computer Science MCQs
Check Data Structure Books
Check Programming Books

Recommended Articles: