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

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.

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.

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

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;

`}`

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.

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__.