# 算法题：如何计算两个数组中的最大求和路径？

2021年3月30日09:48:55 发表评论 861 次浏览

## 本文概述

``````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``````

1. 创建一些变量, 结果, 总和1, 总和2。将结果初始化为0。还将两个变量sum1和sum2初始化为0。此处, sum1和sum2用于分别将元素的和存储在ar1 []和ar2 []中。这些总和在两个公共点之间。
2. 现在运行一个循环以遍历两个数组的元素。遍历时, 按以下顺序比较数组1和数组2的当前元素。
1. 如果当前元素数组1小于的当前元素阵列2, 然后更新总和1, 否则, 如果当前元素为阵列2较小, 然后更新总和2.
2. 如果当前元素数组1和阵列2相同, 则取sum1和sum2的最大值, 并将其加到结果中。还将公共元素添加到结果中。
3. 这一步可以比作两个合并已排序数组, 如果要处理两个当前数组索引中最小的元素, 则可以保证如果有任何公共元素, 它将被一起处理, 因此可以处理两个公共元素之间的元素之和。

## 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
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
int temp = i;
while (i < m && ar1[i] == ar2[j])
sum1 += ar1[i++];

while (j < n && ar1[temp] == ar2[j])
sum2 += ar2[j++];

result += max(sum1, sum2);

sum1 = 0, sum2 = 0;
}
}

// 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
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
int temp = i;
while (i < m && ar1[i] == ar2[j])
sum1 += ar1[i++];

while (j < n && ar1[temp] == ar2[j])
sum2 += ar2[j++];

result += max(sum1, sum2);

sum1 = 0 ;
sum2 = 0 ;
}
}

// 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``````

## python

``````# 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 sum1
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)

# Update sum1 and sum2 for elements after this intersection point
sum1, sum2 = 0 , 0

# Keep updating result while there are more common elements
temp = i
while i < m and ar1[i] = = ar2[j]:
sum1 + = ar1[i];
i + = 1
while j<n and ar1[temp] = = ar2[j]:
sum2 + = ar2[j]
j + = 1
result + = max (sum1, sum2)
sum1 = sum2 = 0 ;

# 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
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
int temp = i;
while (i < m && ar1[i] == ar2[j])
sum1 += ar1[i++];

while (j < n && ar1[temp] == ar2[j])
sum2 += ar2[j++];

result += max(sum1, sum2);

sum1 = 0;
sum2 = 0;
}
}

// 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 )
{

// ar1[] to sum1
if ( \$ar1 [ \$i ] < \$ar2 [ \$j ])
\$sum1 += \$ar1 [ \$i ++];

// 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
\$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
\$temp = \$i ;
while ( \$i < \$m && \$ar1 [ \$i ] == \$ar2 [ \$j ])
\$sum1 += \$ar1 [ \$i ++];

while ( \$j < \$n && \$ar1 [ \$temp ] == \$ar2 [ \$j ])
\$sum2 += \$ar2 [ \$j ++];

\$result += max( \$sum1 , \$sum2 );

\$sum1 = 0;
\$sum2 = 0;
}
}

// 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.
?>``````

``Maximum sum path is 122``

• 空间复杂度：O(1)。
不需要任何额外的空间, 因此空间复杂度是恒定的。
• 时间复杂度：O(m + n)。
在while循环的每次迭代中, 都会处理两个数组之一的元素。总共有m + n个元素。因此, 时间复杂度为O(m + n)。