Suma máxima de prefijos posible al fusionar dos arrays dadas

Posted on by Rudeus Greyrat

Dados dos arreglos A[] y B[] que consisten en N y M enteros respectivamente, la tarea es calcular la suma máxima de prefijos que se puede obtener al fusionar los dos arreglos.

Ejemplos:

Entrada: A[] = {2, -1, 4, -5}, B[]={4, -3, 12, 4, -3}
Salida: 22
Explicación:  fusionar las dos arrays para generar la secuencia {2 , 4, -1, -3, 4, 12, 4, -5, -3}. Suma máxima de prefijos = Suma de {arr[0], …, arr[6]} = 22.

Entrada: A[] = {2, 1, 13, 5, 14}, B={-1, 4, -13}
Salida: 38
Explicación: fusionar las dos arrays para generar la secuencia {2, 1, -1, 13, 5, 14, -13}. Suma máxima de prefijos = Suma de {arr[0], …, arr[6]} = 38.

Enfoque ingenuo: el enfoque más simple es usar Recursion , que se puede optimizar usando Memoization . Siga los pasos a continuación para resolver el problema:

  • Inicializa un map<pair<int, int>, int> dp[] para memorizarlo.
  • Defina una función recursiva, digamos maxPresum(x, y) para encontrar la suma máxima de prefijos:
    • Si ya se calculó dp[{x, y} ] , devuelva dp[{x, y}].
    • De lo contrario, si x==N || y==M, luego devuelve 0 .
    • Actualice dp[{x, y}] como dp[{x, y}] = max(dp[{x, y}, a[x]+maxPresum(x+1, y), b[y]+maxPresum( x, y+1)) y luego devuelve dp[{x, y}].
  • Imprime la suma máxima de prefijos como maxPresum(0, 0) .

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ implementation of above approach
#include <bits/stdc++.h>
 
#define int long long
using namespace std;
 
// Stores the dp states
map<pair<int, int>, int> dp;
 
// Recursive Function to calculate the maximum
// prefix sum obtained by merging two arrays
int maxPreSum(vector<int> a, vector<int> b,
              int x, int y)
{
    // If subproblem is already computed
    if (dp.find({ x, y }) != dp.end())
        return dp[{ x, y }];
 
    // If x >= N or y >= M
    if (x == a.size() && y == b.size())
        return 0;
 
    int curr = dp[{ x, y }];
 
    // If x < N
    if (x == a.size()) {
        curr = max(curr, b[y]
                             + maxPreSum(a, b, x, y + 1));
    }
    // If y<M
    else if (y == b.size()) {
        curr = max(curr,
                   a[x] + maxPreSum(a, b, x + 1, y));
    }
 
    // Otherwise
    else {
        curr = max({ curr,
                     a[x] + maxPreSum(a, b, x + 1, y),
                     b[y] + maxPreSum(a, b, x, y + 1) });
    }
    return dp[{ x, y }] = curr;
}
// Driver Code
signed main()
{
    vector<int> A = { 2, 1, 13, 5, 14 };
    vector<int> B = { -1, 4, -13 };
    cout << maxPreSum(A, B, 0, 0) << endl;
    return 0;
}

C#

// C# implementation of above approach
using System;
using System.Collections.Generic;
 
class GFG{
     
// Stores the dp states
static Dictionary<Tuple<int,
                        int>, int> dp = new Dictionary<Tuple<int,
                                                             int>, int>();
 
// Recursive Function to calculate the maximum
// prefix sum obtained by merging two arrays
static int maxPreSum(int[] a, int[] b, int x, int y)
{
     
    // If subproblem is already computed
    if (dp.ContainsKey(new Tuple<int, int>(x, y)))
        return dp[new Tuple<int, int>(x, y)];
     
    // If x >= N or y >= M
    if (x == a.Length && y == b.Length)
        return 0;
     
    int curr = 0;
    if (dp.ContainsKey(new Tuple<int, int>(x, y)))
    {
        curr = dp[new Tuple<int, int>(x, y)];
    }
     
    // If x < N
    if (x == a.Length)
    {
        curr = Math.Max(curr, b[y] + maxPreSum(
            a, b, x, y + 1));
    }
     
    // If y<M
    else if (y == b.Length)
    {
        curr = Math.Max(curr, a[x] + maxPreSum(
            a, b, x + 1, y));
    }
     
    // Otherwise
    else
    {
        int max = Math.Max(a[x] + maxPreSum(a, b, x + 1, y),
                           b[y] + maxPreSum(a, b, x, y + 1));
        curr = Math.Max(curr, max);
    }
    dp[new Tuple<int,int>(x, y)] = curr;
    return dp[new Tuple<int, int>(x, y)];
}
 
// Driver code
static void Main()
{
    int[] A = { 2, 1, 13, 5, 14 };
    int[] B = { -1, 4, -13 };
     
    Console.WriteLine(maxPreSum(A, B, 0, 0));
}
}
 
// This code is contributed by divyesh072019
Producción: 

38

 

Complejidad de Tiempo: O(N·M)
Espacio Auxiliar: O(N*M)

Enfoque eficiente: el enfoque anterior se puede optimizar en función de la observación de que la suma máxima de prefijos es igual a la suma de la suma máxima de prefijos de las arrays A[] y B[] . Siga los pasos a continuación para resolver el problema:

  • Calcule la suma máxima de prefijos de la array A[] y guárdela en una variable, digamos X.
  • Calcule la suma máxima de prefijos de la array B[] y guárdela en una variable, digamos Y.
  • Imprime la suma de X e Y.

A continuación se muestra la implementación del enfoque anterior: 

C++

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
int maxPresum(vector<int> a, vector<int> b)
{
    // Stores the maximum prefix
    // sum of the array A[]
    int X = max(a[0], 0);
 
    // Traverse the array A[]
    for (int i = 1; i < a.size(); i++) {
        a[i] += a[i - 1];
        X = max(X, a[i]);
    }
 
    // Stores the maximum prefix
    // sum of the array B[]
    int Y = max(b[0], 0);
 
    // Traverse the array B[]
    for (int i = 1; i < b.size(); i++) {
        b[i] += b[i - 1];
        Y = max(Y, b[i]);
    }
    return X + Y;
}
 
// Driver code
int main()
{
    vector<int> A = { 2, -1, 4, -5 };
    vector<int> B = { 4, -3, 12, 4, -3 };
    cout << maxPresum(A, B) << endl;
}

Java

// Java Program to implement
// the above approach
import java.util.*;
class GFG {
 
  static int maxPresum(int [] a, int [] b)
  {
     
    // Stores the maximum prefix
    // sum of the array A[]
    int X = Math.max(a[0], 0);
 
    // Traverse the array A[]
    for (int i = 1; i < a.length; i++)
    {
      a[i] += a[i - 1];
      X = Math.max(X, a[i]);
    }
 
    // Stores the maximum prefix
    // sum of the array B[]
    int Y = Math.max(b[0], 0);
 
    // Traverse the array B[]
    for (int i = 1; i < b.length; i++) {
      b[i] += b[i - 1];
      Y = Math.max(Y, b[i]);
    }
    return X + Y;
  }
 
  // Driver code
  public static void main(String [] args)
  {
    int [] A = { 2, -1, 4, -5 };
    int [] B = { 4, -3, 12, 4, -3 };
    System.out.print(maxPresum(A, B));
  }
}
 
// This code is contributed by ukasp.

Python3

# Python3 implementation of the
# above approach
 
def maxPresum(a, b) :
     
    # Stores the maximum prefix
    # sum of the array A[]
    X = max(a[0], 0)
 
    # Traverse the array A[]
    for i in range(1, len(a)):
        a[i] += a[i - 1]
        X = max(X, a[i])
     
    # Stores the maximum prefix
    # sum of the array B[]
    Y = max(b[0], 0)
 
    # Traverse the array B[]
    for i in range(1, len(b)):
        b[i] += b[i - 1]
        Y = max(Y, b[i])
     
    return X + Y
 
# Driver code
 
A = [ 2, -1, 4, -5 ]
B = [ 4, -3, 12, 4, -3 ]
print(maxPresum(A, B))
 
# This code is contributed by code_hunt.

C#

// C# Program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG {
 
  static int maxPresum(List<int> a, List<int> b)
  {
     
    // Stores the maximum prefix
    // sum of the array A[]
    int X = Math.Max(a[0], 0);
 
    // Traverse the array A[]
    for (int i = 1; i < a.Count; i++)
    {
      a[i] += a[i - 1];
      X = Math.Max(X, a[i]);
    }
 
    // Stores the maximum prefix
    // sum of the array B[]
    int Y = Math.Max(b[0], 0);
 
    // Traverse the array B[]
    for (int i = 1; i < b.Count; i++) {
      b[i] += b[i - 1];
      Y = Math.Max(Y, b[i]);
    }
    return X + Y;
  }
 
  // Driver code
  static void Main()
  {
    List<int> A = new List<int>(new int[]{ 2, -1, 4, -5 });
    List<int> B = new List<int>(new int[]{ 4, -3, 12, 4, -3 });
    Console.WriteLine(maxPresum(A, B));
  }
}
 
// This code is contributed by divyeshrabadiya07.

Javascript

<script>
 
    // Javascript Program to implement
    // the above approach
     
    function maxPresum(a, b)
    {
 
      // Stores the maximum prefix
      // sum of the array A[]
      let X = Math.max(a[0], 0);
 
      // Traverse the array A[]
      for (let i = 1; i < a.length; i++)
      {
        a[i] += a[i - 1];
        X = Math.max(X, a[i]);
      }
 
      // Stores the maximum prefix
      // sum of the array B[]
      let Y = Math.max(b[0], 0);
 
      // Traverse the array B[]
      for (let i = 1; i < b.length; i++) {
        b[i] += b[i - 1];
        Y = Math.max(Y, b[i]);
      }
      return X + Y;
    }
     
    let A = [ 2, -1, 4, -5 ];
    let B = [ 4, -3, 12, 4, -3 ];
    document.write(maxPresum(A, B));
   
</script>
Producción: 

22

 

Complejidad temporal: O(M+N)
Espacio auxiliar: O(1) 

Publicación traducida automáticamente

Artículo escrito por ashutoshrathi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *