Dadas dos arrays de enteros A[] y B[] de diferente longitud N y M respectivamente, la tarea es elegir cualquier subsecuencia de la misma longitud de cada array de modo que se maximice la suma del producto de pares en los índices correspondientes en la subsecuencia.
Ejemplo:
Entrada: A = {4, -1, -3, 3}, B = {-4, 0, 5}
Salida: 27
Explicación: Elegir la subsecuencia {-3, 3} de A y la subsecuencia {-4, 5} de B dará la suma máxima,
es decir = (-3)*(-4) + 3*5 = 12 + 15 = 27Entrada: A = {-5, -1}, B = {2, 1, 4}
Salida: -1
Explicación: La suma máxima de productos posible es (-1)*1 = -1
Enfoque ingenuo : cuando se observa cuidadosamente, en realidad necesitamos encontrar subsecuencias óptimas de igual longitud (> = 1) de cada array, de modo que la suma de los productos de los elementos de estas subsecuencias sea máxima.
Entonces, al usar el método de éxito y prueba, podemos usar un enfoque recursivo para «elegir o no elegir» cada elemento de ambas arrays y encontrar la subsecuencia óptima de todas las subsecuencias posibles .
A continuación se muestra la implementación del enfoque recursivo.
C++
// C++ program to Find the maximum summation of
// products of pair of elements from two arrays
// with negative numbers.
#include <bits/stdc++.h>
using namespace std;
int MaxSOP(vector<int>& a, vector<int>& b,
int n, int m,
int taken)
{
// To ensure we take
// at least one element
if ((n == 0 || m == 0) && taken == 0)
return -9999999;
// Else if we cant take
// any more elements that
// is come to an end
// of any array return 0
else if ((n == 0 || m == 0)
&& taken != 0)
return 0;
// Take the product & increment taken
// skip element from a[]
// skip element from b[]
return max(
{ a[n - 1] * b[m - 1]
+ MaxSOP(a, b, n - 1,
m - 1, taken + 1),
MaxSOP(a, b, n - 1, m, taken),
MaxSOP(a, b, n, m - 1, taken) });
}
// Driver code
int main()
{
vector<int> a = { 4, -1, -3, 3 };
vector<int> b = { -4, 0, 5 };
int ans = MaxSOP(a, b, a.size(),
b.size(), 0);
cout << ans << endl;
return 0;
}
Java
// JAVA program to Find the maximum summation of
// products of pair of elements from two arrays
// with negative numbers.
import java.util.*;
class GFG {
public static int MaxSOP(int a[], int b[], int n, int m,
int taken)
{
// To ensure we take
// at least one element
if ((n == 0 || m == 0) && taken == 0)
return -9999999;
// Else if we cant take
// any more elements that
// is come to an end
// of any array return 0
else if ((n == 0 || m == 0) && taken != 0)
return 0;
// Take the product & increment taken
// skip element from a[]
// skip element from b[]
return Math.max(
Math.max(
a[n - 1] * b[m - 1]
+ MaxSOP(a, b, n - 1, m - 1, taken + 1),
MaxSOP(a, b, n - 1, m, taken)),
MaxSOP(a, b, n, m - 1, taken));
}
// Driver code
public static void main(String[] args)
{
int a[] = { 4, -1, -3, 3 };
int b[] = { -4, 0, 5 };
int ans = MaxSOP(a, b, a.length, b.length, 0);
System.out.print(ans);
}
}
// This code is contributed by rakeshsahni
Python3
# Python3 program to Find the maximum summation of # products of pair of elements from two arrays # with negative numbers. def MaxSOP(a, b, n, m, taken): # To ensure we take # at least one element if ((n == 0 or m == 0) and taken == 0): return -9999999 # Else if we cant take # any more elements that # is come to an end # of any array return 0 elif ((n == 0 or m == 0) and taken != 0): return 0 # Take the product & increment taken # skip element from a[] # skip element from b[] return max(a[n - 1] * b[m - 1] + MaxSOP(a, b, n - 1,m - 1, taken + 1),MaxSOP(a, b, n - 1, m, taken),MaxSOP(a, b, n, m - 1, taken)) # Driver code a = [ 4, -1, -3, 3 ] b = [ -4, 0, 5 ] ans = MaxSOP(a, b, len(a), len(b), 0) print(ans) # This code is contributed by shinjanpatra
C#
// C# program to Find the maximum summation of
// products of pair of elements from two arrays
// with negative numbers.
using System;
class GFG {
static int MaxSOP(int[] a, int[] b, int n, int m,
int taken)
{
// To ensure we take
// at least one element
if ((n == 0 || m == 0) && taken == 0)
return -9999999;
// Else if we cant take
// any more elements that
// is come to an end
// of any array return 0
else if ((n == 0 || m == 0) && taken != 0)
return 0;
// Take the product & increment taken
// skip element from a[]
// skip element from b[]
return Math.Max(
a[n - 1] * b[m - 1]
+ MaxSOP(a, b, n - 1, m - 1, taken + 1),
Math.Max(MaxSOP(a, b, n - 1, m, taken),
MaxSOP(a, b, n, m - 1, taken)));
}
// Driver code
public static void Main()
{
int[] a = { 4, -1, -3, 3 };
int[] b = { -4, 0, 5 };
int ans = MaxSOP(a, b, a.Length, b.Length, 0);
Console.Write(ans);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript program to Find the maximum summation of
// products of pair of elements from two arrays
// with negative numbers.
function MaxSOP(a, b, n, m, taken)
{
// To ensure we take
// at least one element
if ((n == 0 || m == 0) && taken == 0)
return -9999999;
// Else if we cant take
// any more elements that
// is come to an end
// of any array return 0
else if ((n == 0 || m == 0)
&& taken != 0)
return 0;
// Take the product & increment taken
// skip element from a[]
// skip element from b[]
return Math.max(a[n - 1] * b[m - 1]
+ MaxSOP(a, b, n - 1,
m - 1, taken + 1),
MaxSOP(a, b, n - 1, m, taken),
MaxSOP(a, b, n, m - 1, taken));
}
// Driver code
let a = [ 4, -1, -3, 3 ]
let b = [ -4, 0, 5 ]
let ans = MaxSOP(a, b, a.length, b.length, 0)
document.write(ans,"</br>")
// This code is contributed by shinjanpatra
</script>
Producción
27
Complejidad temporal: O(3 N ), ya que estamos llamando a la función 3 veces.
Espacio auxiliar : O (1) (la pila de recursividad no se tiene en cuenta)
Enfoque eficiente : la complejidad de tiempo exponencial del enfoque Naive, debido a la recursividad, se puede optimizar con la programación dinámica .
Memorice el código recursivo y almacene los resultados en una array, de modo que cuando se encuentre un subproblema superpuesto , devuelva directamente el resultado de la array. Esto reducirá la profundidad de la recursividad y reducirá la complejidad del tiempo.
Como tenemos tres parámetros cambiantes, necesitaremos una array DP 3D para almacenar los valores
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to Find the maximum summation of
// products of pair of elements from two arrays
// with negative numbers.
#include <bits/stdc++.h>
using namespace std;
// 3D array for memoization
int t[101][101][101];
int MaxSOP(vector<int>& a, vector<int>& b,
int n, int m,
int taken)
{
// If taken = 0, therefore empty subsequence
// So return highly negative value
if ((n == 0 || m == 0) && taken == 0)
return -9999999;
// Else if we cant take any more elements
// that is come to an end
// of any array return 0
else if ((n == 0 || m == 0) && taken != 0)
return 0;
if (t[n][m][taken] != -1)
// If value is previously calculated
// return it directly
return t[n][m][taken];
return t[n][m][taken]
= max({ a[n - 1] * b[m - 1]
+ MaxSOP(a, b, n - 1,
m - 1,
taken + 1),
MaxSOP(a, b, n - 1, m, taken),
MaxSOP(a, b, n, m - 1, taken) });
}
// Driver code
int main()
{
vector<int> a = { 4, -1, -3, 3 };
vector<int> b = { -4, 0, 5 };
memset(t, -1, sizeof(t));
int ans = MaxSOP(a, b, a.size(),
b.size(), 0);
cout << ans << endl;
return 0;
}
Java
// Java program to Find the maximum summation of
// products of pair of elements from two arrays
// with negative numbers.
import java.util.*;
public class GFG {
// 3D array for memoization
static int t[][][] = new int[101][101][101];
static int MaxSOP(int[] a, int[] b, int n, int m,
int taken)
{
// If taken = 0, therefore empty subsequence
// So return highly negative value
if ((n == 0 || m == 0) && taken == 0)
return -9999999;
// Else if we cant take any more elements
// that is come to an end
// of any array return 0
else if ((n == 0 || m == 0) && taken != 0)
return 0;
if (t[n][m][taken] != -1)
// If value is previously calculated
// return it directly
return t[n][m][taken];
return t[n][m][taken]
= Math.max(
a[n - 1] * b[m - 1]
+ MaxSOP(a, b, n - 1, m - 1, taken + 1),
Math.max(MaxSOP(a, b, n - 1, m, taken),
MaxSOP(a, b, n, m - 1, taken)));
}
// Driver code
public static void main(String args[])
{
int[] a = { 4, -1, -3, 3 };
int[] b = { -4, 0, 5 };
for (int i = 0; i < 101; i++) {
for (int j = 0; j < 101; j++) {
for (int k = 0; k < 101; k++) {
t[i][j][k] = -1;
}
}
}
int ans = MaxSOP(a, b, a.length, b.length, 0);
System.out.println(ans);
}
}
// This code is contributed by Samim Hossain Mondal.
Python3
# Python program to Find the maximum summation of # products of pair of elements from two arrays # with negative numbers. # 3D array for memoization t = [[ [-1 for col in range(101)] for col in range(101)] for row in range(101)] def MaxSOP(a, b, n, m, taken): global t # If taken = 0, therefore empty subsequence # So return highly negative value if ((n == 0 or m == 0) and taken == 0): return -9999999 # Else if we cant take any more elements # that is come to an end # of any array return 0 elif ((n == 0 or m == 0) and taken != 0): return 0 if (t[n][m][taken] != -1): # If value is previously calculated # return it directly return t[n][m][taken] t[n][m][taken] = max(max(a[n - 1] * b[m - 1] + MaxSOP(a, b, n - 1,m - 1,taken + 1),MaxSOP(a, b, n - 1, m, taken)),MaxSOP(a, b, n, m - 1, taken)) return t[n][m][taken] # Driver code a = [ 4, -1, -3, 3 ] b = [ -4, 0, 5 ] ans = MaxSOP(a, b, len(a), len(b), 0) print(ans) # This code is contributed by shinjanpatra
C#
// C# program to Find the maximum summation of
// products of pair of elements from two arrays
// with negative numbers.
using System;
class GFG {
// 3D array for memoization
static int[, , ] t = new int[101, 101, 101];
static int MaxSOP(int[] a, int[] b, int n, int m,
int taken)
{
// If taken = 0, therefore empty subsequence
// So return highly negative value
if ((n == 0 || m == 0) && taken == 0)
return -9999999;
// Else if we cant take any more elements
// that is come to an end
// of any array return 0
else if ((n == 0 || m == 0) && taken != 0)
return 0;
if (t[n, m, taken] != -1)
// If value is previously calculated
// return it directly
return t[n, m, taken];
return t[n, m, taken]
= Math.Max(
a[n - 1] * b[m - 1]
+ MaxSOP(a, b, n - 1, m - 1, taken + 1),
Math.Max(MaxSOP(a, b, n - 1, m, taken),
MaxSOP(a, b, n, m - 1, taken)));
}
// Driver code
public static void Main()
{
int[] a = { 4, -1, -3, 3 };
int[] b = { -4, 0, 5 };
for (int i = 0; i < 101; i++) {
for (int j = 0; j < 101; j++) {
for (int k = 0; k < 101; k++) {
t[i, j, k] = -1;
}
}
}
int ans = MaxSOP(a, b, a.Length, b.Length, 0);
Console.WriteLine(ans);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript program to Find the maximum summation of
// products of pair of elements from two arrays
// with negative numbers.
// 3D array for memoization
let t = new Array(101);
for(let i = 0; i < 101; i++){
t[i] = new Array(101);
for(let j = 0; j < 101; j++){
t[i][j] = new Array(101).fill(-1);
}
}
function MaxSOP(a, b, n, m, taken)
{
// If taken = 0, therefore empty subsequence
// So return highly negative value
if ((n == 0 || m == 0) && taken == 0)
return -9999999;
// Else if we cant take any more elements
// that is come to an end
// of any array return 0
else if ((n == 0 || m == 0) && taken != 0)
return 0;
if (t[n][m][taken] != -1)
// If value is previously calculated
// return it directly
return t[n][m][taken];
return t[n][m][taken]
= Math.max(Math.max(a[n - 1] * b[m - 1]+ MaxSOP(a, b, n - 1, m - 1,taken + 1),MaxSOP(a, b, n - 1, m, taken)),MaxSOP(a, b, n, m - 1, taken));
}
// Driver code
let a = [ 4, -1, -3, 3 ];a
let b = [ -4, 0, 5 ];
let ans = MaxSOP(a, b, a.length, b.length, 0);
document.write(ans);
// This code is contributed by shinjanpatra
</script>
Producción
27
Complejidad Temporal: O(N 3 ).
Espacio auxiliar: O(N 3 ), para usar la array 3D adicional.
Enfoque más eficiente : este enfoque anterior se puede optimizar aún más al reducir el estado tomado usando la siguiente observación:
En el enfoque de programación dinámica anterior, nos preocupan solo dos estados detake : 0 o no 0.
Entonces, en lugar de mantener múltiples estados detake , puede vincularse a dos estados 0 y 1.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Dp array
int t[101][101][2];
// Function to count the maximum possible sum
int MaxSOP(vector<int>& a, vector<int>& b,
int n, int m, int taken)
{
// If taken==0, therefore empty subsequence
// so return highly negative value
if ((n == 0 || m == 0) && taken == 0)
return -9999999;
// Else if we cant take any more elements
// that is come to an end of any array return 0
else if ((n == 0 || m == 0) && taken != 0)
return 0;
// If the value is pre-calculated
// simply return it
if (t[n][m][taken == 0 ? 0 : 1] != -1)
return t[n][m][taken == 0 ? 0 : 1];
// Return and store the calculated value
return t[n][m][taken == 0 ? 0 : 1]
= max({ a[n - 1] * b[m - 1]
+ MaxSOP(a, b, n - 1, m - 1,
taken + 1),
MaxSOP(a, b, n - 1, m, taken),
MaxSOP(a, b, n, m - 1, taken) });
}
// Driver code
int main()
{
vector<int> a = { 4, -1, -3, 3 };
vector<int> b = { -4, 0, 5 };
memset(t, -1, sizeof(t));
int ans = MaxSOP(a, b, a.size(), b.size(), 0);
cout << ans << endl;
return 0;
}
Java
// Java program to Find the maximum summation of
// products of pair of elements from two arrays
// with negative numbers.
import java.util.*;
class GFG {
// DP array
static int t[][][] = new int[101][101][101];
static int MaxSOP(int[] a, int[] b, int n, int m,
int taken)
{
// If taken = 0, therefore empty subsequence
// So return highly negative value
if ((n == 0 || m == 0) && taken == 0)
return -9999999;
// Else if we cant take any more elements
// that is come to an end
// of any array return 0
else if ((n == 0 || m == 0) && taken != 0)
return 0;
// If value is previously calculated
// return it directly
if (t[n][m][taken == 0 ? 0 : 1] != -1)
return t[n][m][taken == 0 ? 0 : 1];
return t[n][m][taken == 0 ? 0 : 1]
= Math.max(
a[n - 1] * b[m - 1]
+ MaxSOP(a, b, n - 1, m - 1, taken + 1),
Math.max(MaxSOP(a, b, n - 1, m, taken),
MaxSOP(a, b, n, m - 1, taken)));
}
// Driver code
public static void main(String args[])
{
int[] a = { 4, -1, -3, 3 };
int[] b = { -4, 0, 5 };
for (int i = 0; i < 101; i++) {
for (int j = 0; j < 101; j++) {
for (int k = 0; k < 101; k++) {
t[i][j][k] = -1;
}
}
}
int ans = MaxSOP(a, b, a.length, b.length, 0);
System.out.println(ans);
}
}
// This code is contributed by Karandeep1234
Python3
# Python 3 program for the above approach import math # DP array t = [[[0] * 101] * 101] * 101 def MaxSOP(a, b, n, m, taken): # If taken = 0, therefore empty subsequence # So return highly negative value if ((n == 0 or m == 0) and taken == 0): return -9999999 # Else if we cant take any more elements # that is come to an end # of any array return 0 elif ((n == 0 or m == 0) and taken != 0) : return 0 # If value is previously calculated # return it directly if (t[n][m][0 if taken == 0 else 1] != -1): return t[n][m][0 if taken == 0 else 1] return max(a[n - 1] * b[m - 1] + MaxSOP(a, b, n - 1, m - 1, taken + 1), max(MaxSOP(a, b, n - 1, m, taken), MaxSOP(a, b, n, m - 1, taken))) # Driver code if __name__ == "__main__": a = [ 4, -1, -3, 3 ] b = [ -4, 0, 5 ] for i in range(101) : for j in range(101) : for k in range(101) : t[i][j][k] = -1 ans = MaxSOP(a, b, len(a), len(b), 0) print(ans) # This code is contributed by code_hunt.
C#
// C# code to implement the approach
using System;
using System.Collections.Generic;
class GFG {
// Dp array
static int[, , ] t = new int[101, 101, 2];
// Function to count the maximum possible sum
static int MaxSOP(List<int> a, List<int> b, int n,
int m, int taken)
{
// If taken==0, therefore empty subsequence
// so return highly negative value
if ((n == 0 || m == 0) && taken == 0)
return -9999999;
// Else if we cant take any more elements
// that is come to an end of any array return 0
else if ((n == 0 || m == 0) && taken != 0)
return 0;
// If the value is pre-calculated
// simply return it
if (t[n, m, taken == 0 ? 0 : 1] != -1)
return t[n, m, taken == 0 ? 0 : 1];
// Return and store the calculated value
return t[n, m, taken == 0 ? 0 : 1] = Math.Max(
Math.Max(a[n - 1] * b[m - 1]
+ MaxSOP(a, b, n - 1, m - 1,
taken + 1),
MaxSOP(a, b, n - 1, m, taken)),
MaxSOP(a, b, n, m - 1, taken));
}
// Driver code
public static void Main()
{
List<int> a = new List<int>() { 4, -1, -3, 3 };
List<int> b = new List<int>() { -4, 0, 5 };
for (int i = 0; i < 101; i++)
for (int j = 0; j < 101; j++)
for (int k = 0; k < 2; k++)
t[i, j, k] = -1;
int ans = MaxSOP(a, b, a.Count, b.Count, 0);
Console.Write(ans);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript program for the above approach
// DP array
let t = new Array(101);
for(let i = 0; i < 101; i++)
{
t[i] = new Array(101);
for(let j = 0; j < 101; j++)
{
t[i][j] = new Array(2).fill(0);
}
}
function MaxSOP(a, b, n, m, taken){
// If taken = 0, therefore empty subsequence
// So return highly negative value
if ((n == 0 || m == 0) && taken == 0)
return -9999999
// Else if we cant take any more elements
// that is come to an end
// of any array return 0
else if ((n == 0 || m == 0) && taken != 0)
return 0
// If value is previously calculated
// return it directly
if (t[n][m][taken == 0 ? 0 : 1] != -1)
return t[n][m][taken == 0 ? 0 : 1]
return Math.max(a[n - 1] * b[m - 1] + MaxSOP(a, b, n - 1, m - 1, taken + 1), Math.max(MaxSOP(a, b, n - 1, m, taken), MaxSOP(a, b, n, m - 1, taken)))
}
// Driver code
let a = [ 4, -1, -3, 3 ]
let b = [ -4, 0, 5 ]
for(let i = 0; i < 101; i++)
{
for(let j = 0; j < 101; j++)
{
for(let k = 0; k < 101; k++)
{
t[i][j][k] = -1
}
}
}
let ans = MaxSOP(a, b, a.length, b.length, 0)
document.write(ans)
// This code is contributed by shinjanpatra
</script>
Producción
27
Complejidad temporal: O(N*M)
Espacio auxiliar: O(N*M)