# 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:

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
```
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.

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. 