Dadas dos arrays a[] y b[] y un entero K , la tarea es encontrar la longitud de la subsecuencia común más larga tal que la suma de los elementos sea igual a K.
Ejemplos:
Entrada: a[] = { 9, 11, 2, 1, 6, 2, 7}, b[] = {1, 2, 6, 9, 2, 3, 11, 7}, K = 18
Salida: 3
Explicación: La subsecuencia { 11, 7 } y { 9, 2, 7 } tienen una suma igual a 18.
Entre ellos { 9, 2, 7 } es el más largo. Por lo tanto, la salida será 3.Entrada: a[] = { 2, 5, 2, 5, 7, 9, 4, 2}, b[] = { 1, 6, 2, 7, 8 }, K = 8
Salida: -1
Enfoque: El enfoque de la solución se basa en el concepto de la subsecuencia común más larga y debemos verificar si la suma de los elementos de la subsecuencia es igual al valor dado. Siga los pasos que se mencionan a continuación;
- Considere la suma variable inicializada al valor dado.
- Cada vez que se incluyan elementos en una subsecuencia, disminuya el valor de la suma por este elemento.
- En la condición base, verifique si el valor de la suma es 0 , lo que implica que esta subsecuencia tiene una suma igual a K. Por lo tanto, devuelva 0 cuando la suma sea cero, de lo contrario, devuelva INT_MIN
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;
int solve(int a[], int b[], int i, int j, int sum)
{
if (sum == 0)
return 0;
if (sum < 0)
return INT_MIN;
if (i == 0 || j == 0) {
if (sum == 0)
return 0;
else
return INT_MIN;
}
// If values are same then we can include this
// or also can't include this
if (a[i - 1] == b[j - 1])
return max(
1 + solve(a, b, i - 1, j - 1, sum - a[i - 1]),
solve(a, b, i - 1, j - 1, sum));
return max(solve(a, b, i - 1, j, sum),
solve(a, b, i, j - 1, sum));
}
// Driver code
int main()
{
int a[] = { 9, 11, 2, 1, 6, 2, 7 };
int b[] = { 1, 2, 6, 9, 2, 3, 11, 7 };
int n = sizeof(a) / sizeof(int);
int m = sizeof(b) / sizeof(int);
int sum = 18;
int ans = solve(a, b, n, m, sum);
if (ans >= 0)
cout << ans << endl;
else
cout << -1;
return 0;
}
Java
// Java code to implement the approach
import java.io.*;
class GFG {
static int solve(int a[], int b[], int i, int j, int sum)
{
if (sum == 0)
return 0;
if (sum < 0)
return Integer.MIN_VALUE;
if (i == 0 || j == 0) {
if (sum == 0)
return 0;
else
return Integer.MIN_VALUE;
}
// If values are same then we can include this
// or also can't include this
if (a[i - 1] == b[j - 1])
return Math.max(
1 + solve(a, b, i - 1, j - 1, sum - a[i - 1]),
solve(a, b, i - 1, j - 1, sum));
return Math.max(solve(a, b, i - 1, j, sum),
solve(a, b, i, j - 1, sum));
}
// Driver code
public static void main (String[] args) {
int a[] = { 9, 11, 2, 1, 6, 2, 7 };
int b[] = { 1, 2, 6, 9, 2, 3, 11, 7 };
int n = a.length;
int m = b.length;
int sum = 18;
int ans = solve(a, b, n, m, sum);
if (ans >= 0)
System.out.print(ans);
else
System.out.print(-1);
}
}
// This code is contributed by hrithikgarg03188.
Python3
# Python code for the above approach def solve(a, b, i, j, sum): if sum == 0: return 0 if sum < 0: return -2147483648 if i == 0 or j == 0: if sum == 0: return 0 else: return -2147483648 # If values are same then we can include this # or also can't include this if (a[i - 1] == b[j - 1]): return max( 1 + solve(a, b, i - 1, j - 1, sum - a[i - 1]), solve(a, b, i - 1, j - 1, sum)) return max(solve(a, b, i - 1, j, sum), solve(a, b, i, j - 1, sum)) # Driver code a = [9, 11, 2, 1, 6, 2, 7] b = [1, 2, 6, 9, 2, 3, 11, 7] n = len(a) m = len(b) sum = 18 ans = solve(a, b, n, m, sum) if (ans >= 0): print(ans) else: print(-1) # This code is contributed by Potta Lokesh
C#
// C# code to implement the approach
using System;
class GFG {
static int solve(int[] a, int[] b, int i, int j,
int sum)
{
if (sum == 0)
return 0;
if (sum < 0)
return Int32.MinValue;
if (i == 0 || j == 0) {
if (sum == 0)
return 0;
else
return Int32.MinValue;
}
// If values are same then we can include this
// or also can't include this
if (a[i - 1] == b[j - 1])
return Math.Max(1
+ solve(a, b, i - 1, j - 1,
sum - a[i - 1]),
solve(a, b, i - 1, j - 1, sum));
return Math.Max(solve(a, b, i - 1, j, sum),
solve(a, b, i, j - 1, sum));
}
// Driver code
public static void Main()
{
int[] a = { 9, 11, 2, 1, 6, 2, 7 };
int[] b = { 1, 2, 6, 9, 2, 3, 11, 7 };
int n = a.Length;
int m = b.Length;
int sum = 18;
int ans = solve(a, b, n, m, sum);
if (ans >= 0)
Console.Write(ans);
else
Console.Write(-1);
}
}
// This code is contributed by Samim Hossain Mondal..
Javascript
<script>
// JavaScript code to implement the approach
const INT_MIN = -2147483648;
const solve = (a, b, i, j, sum) => {
if (sum == 0)
return 0;
if (sum < 0)
return INT_MIN;
if (i == 0 || j == 0) {
if (sum == 0)
return 0;
else
return INT_MIN;
}
// If values are same then we can include this
// or also can't include this
if (a[i - 1] == b[j - 1])
return Math.max(
1 + solve(a, b, i - 1, j - 1, sum - a[i - 1]),
solve(a, b, i - 1, j - 1, sum));
return Math.max(solve(a, b, i - 1, j, sum),
solve(a, b, i, j - 1, sum));
}
// Driver code
let a = [9, 11, 2, 1, 6, 2, 7];
let b = [1, 2, 6, 9, 2, 3, 11, 7];
let n = a.length;
let m = b.length;
let sum = 18;
let ans = solve(a, b, n, m, sum);
if (ans >= 0)
document.write(`${ans}`);
else
document.write("-1");
// This code is contributed by rakeshsahani..
</script>
Producción
3
Complejidad de tiempo: O(2 N ), N tamaño máximo entre ambas arrays
Espacio auxiliar: O(1)
Enfoque eficiente: un enfoque eficiente es usar la memorización para reducir la complejidad del tiempo donde cada estado almacena la longitud máxima de una subsecuencia que tiene una suma. Utilice el mapa para lograr esto.
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;
// Function to find longest common subsequence having sum
// equal to given value
int solve(int a[], int b[], int i, int j, int sum,
map<string, int>& mp)
{
if (sum == 0)
return 0;
if (sum < 0)
return INT_MIN;
if (i == 0 || j == 0) {
if (sum == 0)
return 0;
else
return INT_MIN;
}
string temp = to_string(i) + '#'
+ to_string(j) + '#'
+ to_string(sum);
if (mp.find(temp) != mp.end())
return mp[temp];
// If values are same then we can include this
// or also can't include this
if (a[i - 1] == b[j - 1])
return mp[temp]
= max(
1 + solve(a, b, i - 1, j - 1,
sum - a[i - 1], mp),
solve(a, b, i - 1, j - 1, sum, mp));
return mp[temp]
= max(solve(a, b, i - 1, j, sum, mp),
solve(a, b, i, j - 1, sum, mp));
}
// Driver code
int main()
{
int a[] = { 9, 11, 2, 1, 6, 2, 7 };
int b[] = { 1, 2, 6, 9, 2, 3, 11, 7 };
map<string, int> mp;
int n = sizeof(a) / sizeof(int);
int m = sizeof(b) / sizeof(int);
int sum = 18;
int ans = solve(a, b, n, m, sum, mp);
if (ans >= 0)
cout << ans << endl;
else
cout << -1;
return 0;
}
Java
// Java code to implement the approach
import java.util.*;
class GFG{
// Function to find longest common subsequence having sum
// equal to given value
static int solve(int a[], int b[], int i, int j, int sum,
HashMap<String, Integer> mp)
{
if (sum == 0)
return 0;
if (sum < 0)
return Integer.MIN_VALUE;
if (i == 0 || j == 0) {
if (sum == 0)
return 0;
else
return Integer.MIN_VALUE;
}
String temp = String.valueOf(i) + '#'
+ String.valueOf(j) + '#'
+ String.valueOf(sum);
if (mp.containsKey(temp))
return mp.get(temp);
// If values are same then we can include this
// or also can't include this
if (a[i - 1] == b[j - 1]) {
mp.put(temp, Math.max(
1 + solve(a, b, i - 1, j - 1,
sum - a[i - 1], mp),
solve(a, b, i - 1, j - 1, sum, mp)));
return mp.get(temp);
}
mp.put(temp, Math.max(solve(a, b, i - 1, j, sum, mp),
solve(a, b, i, j - 1, sum, mp)));
return mp.get(temp);
}
// Driver code
public static void main(String[] args)
{
int a[] = { 9, 11, 2, 1, 6, 2, 7 };
int b[] = { 1, 2, 6, 9, 2, 3, 11, 7 };
HashMap<String, Integer> mp = new HashMap<>();
int n = a.length;
int m = b.length;
int sum = 18;
int ans = solve(a, b, n, m, sum, mp);
if (ans >= 0)
System.out.print(ans +"\n");
else
System.out.print(-1);
}
}
// This code is contributed by shikhasingrajput
Python3
# Python code to implement the approach
# Function to find longest common subsequence having sum
# equal to given value
def solve(a, b, i, j, sum, mp):
if sum == 0:
return 0
if sum < 0:
return -2147483648
if i == 0 or j == 0:
if sum == 0:
return 0
else:
return -2147483648
temp=str(i)+"#"+str(j)+"#"+str(sum)
if(temp in mp):
return mp[temp]
# If values are same then we can include this
# or also can't include this
if (a[i - 1] == b[j - 1]):
mp[temp] = max(1 + solve(a, b, i - 1, j - 1, sum - a[i - 1], mp),solve(a, b, i - 1, j - 1, sum,mp))
return mp[temp]
mp[temp] = max(solve(a, b, i - 1, j, sum,mp),solve(a, b, i, j - 1, sum,mp))
return mp[temp]
# Driver code
a = [9, 11, 2, 1, 6, 2, 7]
b = [1, 2, 6, 9, 2, 3, 11, 7]
n = len(a)
m = len(b)
sum = 18
mp = {}
ans = solve(a, b, n, m, sum, mp)
if (ans >= 0):
print(ans)
else:
print(-1)
# This code is contributed by Pushpesh Raj
C#
// C# code to implement the approach
using System;
using System.Collections.Generic;
class GFG {
// Function to find longest common subsequence having
// sum equal to given value
static int solve(int[] a, int[] b, int i, int j,
int sum, Dictionary<string, int> mp)
{
if (sum == 0)
return 0;
if (sum < 0)
return Int32.MinValue;
if (i == 0 || j == 0) {
if (sum == 0)
return 0;
else
return Int32.MinValue;
}
string temp = i.ToString() + "#" + j.ToString()
+ "#" + sum.ToString();
if (mp.ContainsKey(temp))
return mp[temp];
// If values are same then we can include this
// or also can't include this
if (a[i - 1] == b[j - 1])
return mp[temp] = Math.Max(
1
+ solve(a, b, i - 1, j - 1,
sum - a[i - 1], mp),
solve(a, b, i - 1, j - 1, sum, mp));
return mp[temp]
= Math.Max(solve(a, b, i - 1, j, sum, mp),
solve(a, b, i, j - 1, sum, mp));
}
// Driver code
public static void Main()
{
int[] a = { 9, 11, 2, 1, 6, 2, 7 };
int[] b = { 1, 2, 6, 9, 2, 3, 11, 7 };
Dictionary<string, int> mp
= new Dictionary<string, int>();
int n = a.Length;
int m = b.Length;
int sum = 18;
int ans = solve(a, b, n, m, sum, mp);
if (ans >= 0)
Console.WriteLine(ans);
else
Console.Write(-1);
}
}
// This code is contributed by Samim Hossain Mondal.
Producción
3
Complejidad de Tiempo: O(N*M)
Espacio Auxiliar: O(N * M)