两个数组中的最大求和路径 · GeeksForGeeks 中文系列教程

# 两个数组中的最大求和路径 > 原文： [https://www.geeksforgeeks.org/maximum-sum-path-across-two-arrays/](https://www.geeksforgeeks.org/maximum-sum-path-across-two-arrays/) 给定两个排序的数组，这样该数组可能具有一些公共元素。查找从任何数组的开始到两个数组中的任何一个数组的结尾的最大和路径的和。我们只能在公共元素处从一个数组切换到另一个数组。 **注意**：公用元素不必具有相同的索引。 **预期时间复杂度**：`O(m + n)`，其中`m`是`ar1[]`中的元素数，`n`是`ar2[]`中的元素数。 **示例**： ``` Input: ar1[] = {2, 3, 7, 10, 12} ar2[] = {1, 5, 7, 8} Output: 35 Explanation: 35 is sum of 1 + 5 + 7 + 10 + 12. We start from the first element of arr2 which is 1, then we move to 5, then 7\. From 7, we switch to ar1 (as 7 is common) and traverse 10 and 12. Input: ar1[] = {10, 12} ar2 = {5, 7, 9} Output: 22 Explanation: 22 is the sum of 10 and 12. Since there is no common element, we need to take all elements from the array with more sum. Input: ar1[] = {2, 3, 7, 10, 12, 15, 30, 34} ar2[] = {1, 5, 7, 8, 10, 15, 16, 19} Output: 122 Explanation: 122 is sum of 1, 5, 7, 8, 10, 12, 15, 30, 34 ``` **有效方法**：的想法是做类似于[合并排序](http://geeksquiz.com/merge-sort/)的合并过程的操作。这涉及计算两个数组的所有公共点之间的元素之和。只要有一个共同点，就比较两个和并将两个的最大值相加。 **算法** ： 1. 创建一些变量，`result`，`sum1`，`sum2`。将结果初始化为 0。还将两个变量`sum1`和`sum2`初始化为 0。此处，`sum1`和`sum2`用于分别将元素的和存储在`ar1[]`和`ar2[]`中。这些总和在两个共同点之间。 2. 现在运行一个循环以遍历两个数组的元素。遍历时，按以下顺序比较数组 1 和数组 2 的当前元素。 1. 如果`ar1[]`的当前元素小于`ar2[]`的当前元素，则更新`sum1`，否则，如果`ar2[]`较小，然后更新`sum2`。 2. 如果`ar1[]`和`ar2[]`的当前元素相同，则取`sum1`和`sum2`的最大值，并将其加到结果中。还将公共元素添加到结果中。 3. 可以将此步骤与合并两个*排序的*数组进行比较，如果处理了两个当前数组索引中的最小元素，则可以保证如果有任何公共元素，则将它们一起处理。可以处理两个公共元素之间的元素总和。 **实现**： ## C++ ```cpp #include<iostream> using namespace std; // Utility function to find maximum of two integers int max(int x, int y) { return (x > y)? x : y; } // This function returns the sum of elements on maximum path // from beginning to end int maxPathSum(int ar1[], int ar2[], int m, int n) { // initialize indexes for ar1[] and ar2[] int i = 0, j = 0; // Initialize result and current sum through ar1[] and ar2[]. int result = 0, sum1 = 0, sum2 = 0; // Below 3 loops are similar to merge in merge sort while (i < m && j < n) { // Add elements of ar1[] to sum1 if (ar1[i] < ar2[j]) sum1 += ar1[i++]; // Add elements of ar2[] to sum2 else if (ar1[i] > ar2[j]) sum2 += ar2[j++]; else // we reached a common point { // Take the maximum of two sums and add to result result += max(sum1, sum2); // Update sum1 and sum2 for elements after this // intersection point sum1 = 0, sum2 = 0; // Keep updating result while there are more common // elements while (i < m && j < n && ar1[i] == ar2[j]) { result = result + ar1[i++]; j++; } } } // Add remaining elements of ar1[] while (i < m) sum1 += ar1[i++]; // Add remaining elements of ar2[] while (j < n) sum2 += ar2[j++]; // Add maximum of two sums of remaining elements result += max(sum1, sum2); return result; } // Driver program to test above function int main() { int ar1[] = {2, 3, 7, 10, 12, 15, 30, 34}; int ar2[] = {1, 5, 7, 8, 10, 15, 16, 19}; int m = sizeof(ar1)/sizeof(ar1[0]); int n = sizeof(ar2)/sizeof(ar2[0]); cout << "Maximum sum path is " << maxPathSum(ar1, ar2, m, n); return 0; } ```