Dados dos arreglos ordenados, tales que los arreglos pueden tener algunos elementos comunes. Encuentre la suma de la ruta de suma máxima para alcanzar desde el principio de cualquier array hasta el final de cualquiera de las dos arrays. Podemos cambiar de una array a otra array solo en elementos comunes.
Nota: Los elementos comunes no tienen que estar en los mismos índices.
Complejidad de tiempo esperada: O(m+n) , donde m es el número de elementos en ar1[] y n es el número de elementos en ar2[].
Ejemplos:
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
Enfoque eficiente: la idea es hacer algo similar al proceso de fusión de tipo de fusión . Esto implica calcular la suma de elementos entre todos los puntos comunes de ambas arrays. Siempre que haya un punto en común, compara las dos sumas y suma el máximo de dos al resultado.
Algoritmo :
- Cree algunas variables, resultado , suma1 , suma2 . Inicialice el resultado como 0. También inicialice dos variables sum1 y sum2 como 0. Aquí sum1 y sum2 se usan para almacenar la suma del elemento en ar1[] y ar2[] respectivamente. Estas sumas están entre dos puntos comunes.
- Ahora ejecute un ciclo para atravesar elementos de ambas arrays. Mientras atraviesa, compare los elementos actuales de la array 1 y la array 2 en el siguiente orden.
- Si el elemento actual de la array 1 es más pequeño que el elemento actual de la array 2 , actualice sum1 ; de lo contrario, si el elemento actual de la array 2 es más pequeño, actualice sum2 .
- Si el elemento actual de la array 1 y la array 2 son iguales, tome el máximo de sum1 y sum2 y agréguelo al resultado. También agregue el elemento común al resultado.
- Este paso se puede comparar con la fusión de dos arrays ordenadas . Si se procesa el elemento más pequeño de los dos índices de array actuales, se garantiza que, si hay algún elemento común, se procesarán juntos. Entonces se puede procesar la suma de elementos entre dos elementos comunes.
A continuación se muestra la implementación del código anterior:
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>
Producción
Maximum sum path is 122
Análisis de complejidad :
- Complejidad espacial: O(1).
No se requiere ningún espacio adicional, por lo que la complejidad del espacio es constante. - Complejidad temporal: O(m+n).
En cada iteración de bucles while, se procesa un elemento de cualquiera de las dos arrays. Hay un total de m + n elementos. Por lo tanto, la complejidad del tiempo es O(m+n).
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA