# 兩個數組中的最大求和路徑 > 原文： [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; } ```