给定两个排序的数组，这样这些数组可能有一些公共元素。求从任意数组开始到任意两个数组结束的最大和路径之和。我们只能在公共元素处从一个数组切换到另一个数组。 注： 公共元素不必位于相同的索引中。
null
预期时间复杂度：O（m+n） ，其中m是ar1[]中的元素数，n是ar2[]中的元素数。
例如：
Input: ar1[] = {2, 3, 7, 10, 12} ar2[] = {1, 5, 7, 8}Output: 35Explanation: 35 is sum of 1 + 5 + 7 + 10 + 12.We start from the first element of arr2 which is 1, then wemove 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: 22Explanation: 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: 122Explanation: 122 is sum of 1, 5, 7, 8, 10, 12, 15, 30, 34
有效方法： 这个想法是做一些类似于合并过程的事情 合并排序 。这涉及计算两个数组的所有公共点之间的元素之和。只要有一个共同点，就比较这两个和，并将两个和中的最大值相加。
算法 :
- 创建一些变量， 后果 , sum1 , sum2 .将结果初始化为0。同时将两个变量sum1和sum2初始化为0。这里，sum1和sum2分别用于存储ar1[]和ar2[]中元素的总和。这些总和介于两个共同点之间。
- 现在运行一个循环来遍历两个数组的元素。遍历时，按以下顺序比较数组1和数组2的当前元素。
- 如果当前元素 数组1 小于当前的元素 阵列2 ，然后更新 sum1 ，否则如果当前元素 阵列2 更小，然后更新 sum2 .
- 如果当前元素 数组1 和 阵列2 相同，然后取sum1和sum2的最大值，并将其添加到结果中。还要将公共元素添加到结果中。
- 这一步可以比作两个步骤的合并 分类 数组中，如果处理两个当前数组索引中的最小元素，则可以保证，如果存在任何公共元素，将一起处理。因此，可以处理两个公共元素之间的元素之和。
以下是上述代码的实现：
C++
// C++ program to find maximum sum path #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 //Also add the common element of array, once result += max(sum1, sum2) + ar1[i]; // Update sum1 and sum2 for elements after this // intersection point sum1 = 0; sum2 = 0; //update i and j to move to next element of each array 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 code 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]); // Function call cout << "Maximum sum path is " << maxPathSum(ar1, ar2, m, n); return 0; } |
JAVA
// JAVA program to find maximum sum path class MaximumSumPath { // 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++]; // we reached a common point else { // Take the maximum of two sums and add to // result //Also add the common element of array, once result += max(sum1, sum2) + ar1[i]; // Update sum1 and sum2 for elements after this // intersection point sum1 = 0 ; sum2 = 0 ; //update i and j to move to next element of each array 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 code public static void main(String[] args) { MaximumSumPath sumpath = new MaximumSumPath(); int ar1[] = { 2 , 3 , 7 , 10 , 12 , 15 , 30 , 34 }; int ar2[] = { 1 , 5 , 7 , 8 , 10 , 15 , 16 , 19 }; int m = ar1.length; int n = ar2.length; // Function call System.out.println( "Maximum sum path is :" + sumpath.maxPathSum(ar1, ar2, m, n)); } } // This code has been contributed by Mayank Jaiswal |
Python3
# Python program to find maximum sum path # This function returns the sum of elements on maximum path from # beginning to end def maxPathSum(ar1, ar2, m, n): # initialize indexes for ar1[] and ar2[] i, j = 0 , 0 # Initialize result and current sum through ar1[] and ar2[] result, sum1, sum2 = 0 , 0 , 0 # Below 3 loops are similar to merge in merge sort while (i < m and j < n): # Add elements of ar1[] to sum1 if ar1[i] < ar2[j]: sum1 + = ar1[i] i + = 1 # Add elements of ar2[] to sum2 elif ar1[i] > ar2[j]: sum2 + = ar2[j] j + = 1 else : # we reached a common point # Take the maximum of two sums and add to result result + = max (sum1, sum2) + ar1[i] #update sum1 and sum2 to be considered fresh for next elements sum1 = 0 sum2 = 0 #update i and j to move to next element in each array i + = 1 j + = 1 # Add remaining elements of ar1[] while i < m: sum1 + = ar1[i] i + = 1 # Add remaining elements of b[] while j < n: sum2 + = ar2[j] j + = 1 # Add maximum of two sums of remaining elements result + = max (sum1, sum2) return result # Driver code ar1 = [ 2 , 3 , 7 , 10 , 12 , 15 , 30 , 34 ] ar2 = [ 1 , 5 , 7 , 8 , 10 , 15 , 16 , 19 ] m = len (ar1) n = len (ar2) # Function call print ( "Maximum sum path is" , maxPathSum(ar1, ar2, m, n)) # This code is contributed by __Devesh Agrawal__ |
C#
// C# program for Maximum Sum Path in // Two Arrays using System; class GFG { // Utility function to find maximum // of two integers static 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 static 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++]; // we reached a common point else { // Take the maximum of two sums and add to // result // Also add the common element of array, // once result += max(sum1, sum2) + ar1[i]; // Update sum1 and sum2 for elements after // this intersection point sum1 = 0; sum2 = 0; // update i and j to move to next element of // each array 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 code public static void Main() { int [] ar1 = { 2, 3, 7, 10, 12, 15, 30, 34 }; int [] ar2 = { 1, 5, 7, 8, 10, 15, 16, 19 }; int m = ar1.Length; int n = ar2.Length; // Function call Console.Write( "Maximum sum path is :" + maxPathSum(ar1, ar2, m, n)); } } // This code is contributed by nitin mittal. |
PHP
<?php // PHP Program to find Maximum Sum // Path in Two Arrays // This function returns the sum of // elements on maximum path // from beginning to end function maxPathSum( $ar1 , $ar2 , $m , $n ) { // initialize indexes for // ar1[] and ar2[] $i = 0; $j = 0; // Initialize result and // current sum through ar1[] // and ar2[]. $result = 0; $sum1 = 0; $sum2 = 0; // Below 3 loops are similar // to merge in merge sort while ( $i < $m and $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 ++]; // we reached a // common point else { // Take the maximum of two sums and add to // result //Also add the common element of array, once $result += max( $sum1 , $sum2 ) + $ar1 [ $i ]; // Update sum1 and sum2 for elements after this // intersection point $sum1 = 0; $sum2 = 0; //update i and j to move to next element of each array $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 Code $ar1 = array (2, 3, 7, 10, 12, 15, 30, 34); $ar2 = array (1, 5, 7, 8, 10, 15, 16, 19); $m = count ( $ar1 ); $n = count ( $ar2 ); // Function call echo "Maximum sum path is " , maxPathSum( $ar1 , $ar2 , $m , $n ); // This code is contributed by anuj_67. ?> |
Javascript
<script> // Javascript program to find maximum sum path // Utility function to find maximum of two integers function max(x, y) { return (x > y) ? x : y; } // This function returns the sum of elements // on maximum path from beginning to end function maxPathSum(ar1, ar2, m, n) { // Initialize indexes for ar1[] and ar2[] let i = 0, j = 0; // Initialize result and current sum // through ar1[] and ar2[]. let result = 0, sum1 = 0, sum2 = 0; // Below3 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++]; // We reached a common point else { // Take the maximum of two sums and add to // result //Also add the common element of array, once result += Math.max(sum1, sum2) + ar1[i]; // Update sum1 and sum2 for elements after this // intersection point sum1 = 0; sum2 = 0; //update i and j to move to next element of each array 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 += Math.max(sum1, sum2); return result; } // Driver code let ar1 = [ 2, 3, 7, 10, 12, 15, 30, 34 ]; let ar2 = [ 1, 5, 7, 8, 10, 15, 16, 19 ]; let m = ar1.length; let n = ar2.length; // Function call document.write( "Maximum sum path is " + maxPathSum(ar1, ar2, m, n)); // This code is contributed by Mayank Tyagi </script> |
输出
Maximum sum path is 122
复杂性分析 :
- 空间复杂性： O（1）。 不需要任何额外的空间，因此空间复杂度是恒定的。
- 时间复杂性： O（m+n）。 在while循环的每次迭代中，都会处理来自两个数组中任意一个的元素。共有m+n元素。因此，时间复杂度为O（m+n）。
本文由 皮尤斯·古普塔 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
