C ++中两个数组的最大和路径

问题陈述

给定两个排序的数组，此类数组可能具有一些公共元素。查找从任何数组的开始到两个数组中的任何一个数组的结尾的最大和路径的和。我们只能在公共元素处从一个阵列切换到另一个阵列。注意，公共元素不必位于相同的索引处。

预期的时间复杂度为O（m + n），其中m是arr1 []中的元素数，n是arrs2 []中的元素数

示例

If given input is then output is 35
arr1[] = {2, 3, 7, 10, 12}
ar2[] = {1, 5, 7, 8}
(1 + 5 + 7 + 10 + 12) = 35

• 1.我们从arr2的第一个元素1开始，然后移至5，然后是7。

• 从7开始，我们切换到ar1（常见的是7）并遍历10和12。

算法

• 这个想法是做一些类似于合并排序的合并过程。我们需要计算两个数组所有公共点之间的元素和。每当我们看到一个共同点时，我们都会比较两个总和，并将两个的最大值相加。

• 将结果初始化为0。还将两个变量sum1和sum2初始化为0。此处，sum1和sum2用于将元素的和分别存储在arr1 []和arr2 []中。这些总和介于两个共同点之间

• 现在运行一个循环以遍历两个数组的元素。遍历时比较arr1 []和arr2 []的当前元素

• 如果arr1 []的当前元素小于arr2 []的当前元素，则更新sum1，否则，如果arr2 []的当前元素小于，则更新sum

• 如果arr1 []和arr2 []的当前元素相同，则取sum1和sum2的最大值，并将其加到结果中。还要在结果中添加common元素

示例

#include <bits/stdc++.h>
using namespace std;
int max(int x, int y){
   return (x > y)? x : y;
}
int maxPathSum(int *arr1, int *arr2, int m, int n){
   int i = 0, j = 0;
   int result = 0, sum1 = 0, sum2 = 0;
   while (i < m && j < n) {
      if (arr1[i] < arr2[j]) {
         sum1 += arr1[i++];
      } else if (arr1[i] > arr2[j]) {
         sum2 += arr2[j++];
      } else {
         result += max(sum1, sum2);
         sum1 = 0, sum2 = 0;
         while (i < m && j < n && arr1[i] == arr2[j]) {
            result = result + arr1[i++];
            j++;
         }
      }
   }
   while (i < m) {
      sum1 += arr1[i++];
   }
   while (j < n) {
      sum2 += arr2[j++];
   }
   result += max(sum1, sum2);
   return result;
}
int main(){
   int arr1[] = {2, 3, 7, 10, 12};
   int arr2[] = {1, 5, 7, 8};
   int m = sizeof(arr1)/sizeof(arr1[0]);
   int n = sizeof(arr2)/sizeof(arr2[0]);
   cout << "Maximum sum path = " << maxPathSum(arr1, arr2, m, n) << endl;
   return 0;
}

输出结果

当您编译并执行上述程序时。它产生以下输出-

Maximum sum path = 35