Home » C++ programming language

Learn: **C++ program to find maxsum of double helix** - How to find a path that produces the maximum sum of elements on your path you walked over?

**Question:** Given two finite, strictly increasing, integer sequences. Any common integer between the two sequences constitutes an intersection point; you have to find a path that produces the maximum sum of elements on your path you walked over.

**You can 'walk' over these two sequences in the following way:**

- You may start at the beginning of any of the two sequences. Now start moving forward.
- At each intersection point, you have the choice of either continuing with the same sequence you are currently on, or switching to the other sequence.

**Example:**

Input: A1[] = 1 2 7 11 14 25 A2[] = 1 4 7 9 12 25 30Output : 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.

As we proceed in processing the sequence we sum all elements of sequence 1 and sequence 2 in path1 and path2 respectively till we reach any intersecting point. After reaching any intersecting point we should add greater of path1 or path2 to pathsum and reset path1 = path2 = 0 and start processing sequences further. In the case we end up any sequence we should add all remaining elements of next sequence to its corresponding path and finally check for greater of both the paths and add the greater to pathsum.

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

Are you a blogger? Join our Blogging forum.

Comments and Discussions

We are using Google to publish ads on our website; Google has its own privacy policies. They may save log, cookies on your system. Google may also collect information of your system like IP address, region, city, country. For more details please go through the Google’s privacy policy.