最大和螺旋路径（使用C ++程序）

问题：给定两个有限的，严格增加的整数序列。两个序列之间的任何公共整数都构成一个交点；您必须找到一条在您走过的路径上产生最大元素总和的路径。

您可以通过以下方式“遍历”这两个序列：

1. 您可以从两个序列中的任何一个开始。现在开始前进。

2. 在每个交叉点，您可以选择继续使用当前正在使用的相同序列，或切换到其他序列。

示例

Input:
A1[] = 1 2 7 11 14 25 
A2[] = 1 4 7  9 12 25 30Output : The largest possible sum = 92

想法：我们将维护三个变量path1，path2和pathum。在任何时候，path1都是我们到目前为止所走过的最大数据总和，位于序列1上。path2是我们直到现在为止所走过的最大数据量，位于序列2上。最终结果存储在变量pathum中，通过是path1和path2的最大值。

在处理序列时，我们将路径1和路径2中的序列1和序列2的所有元素求和，直到到达任何相交点。到达任何相交点后，我们应将path1或path2中的较大者添加到pathum中，并重置path1 = path2 = 0，然后进一步开始处理序列。在我们结束任何序列的情况下，我们应该将下一个序列的所有剩余元素添加到其对应的路径中，最后检查两个路径中较大的一个，并将较大的路径添加到pathum中。

C ++程序查找双螺旋的最大和

#include<bits/stdc++.h>
using namespace std;

//计算最大和的函数
int maxSumDHelix(int A1[], int A2[], int n1, int n2)
{
  int i, j = 0, path1 = 0, path2 = 0, pathsum = 0;

    //n1，n2是两个序列的长度
    for(i=0; i<n2; i++)
    {
       //将元素添加到path2-
       path2 += A2[i];

       //将元素添加到pat1-
       while(j<n1 && A1[j] < A2[i])
       {
           path1 += A1[j];
           j++;
       }

       //在交叉点更新
       //path1 path2和pathum-
       if(j<n1 && A1[j]==A2[i])
       {
            path1 += A1[j];
            pathsum += max(path1, path2);

            //重置
            path1 = 0;
            path2 = 0;
            j++;
       }
    }

    // if n1 &amp;gt; n2
    while(j<n1)
    {
        path1 += A1[j];
        j++;
    }
    //最终结果
    pathsum += max(path1, path2);
    return pathsum;
}


//驱动程序
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;
}

输出结果

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