Dada una array arr[] que consta de N enteros y un entero K , la tarea es encontrar la longitud de la subsecuencia más larga con una suma igual a K .
Ejemplos:
Entrada: arr[] = {-4, -2, -2, -1, 6}, K = 0
Salida: 3
Explicación:
La subsecuencia más larga tiene una longitud de 3, que es {-4, -2, 6} con suma 0.
Entrada: arr[] = {-3, 0, 1, 1, 2}, K = 1
Salida: 5
Explicación: La subsecuencia más larga tiene una longitud de 5, que es {-3, 0, 1, 1, 2} teniendo suma 1.
Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todas las subsecuencias posibles de diferentes longitudes y verificar si su suma es igual a K . De todas estas subsecuencias con suma K , encuentre la subsecuencia con la longitud más larga.
Complejidad del tiempo: O(2 N )
Enfoque recursivo y de retroceso: el enfoque básico de este problema es clasificar el vector y encontrar la suma de todas las subsecuencias posibles y seleccionar la subsecuencia con la longitud máxima que tenga la suma dada. Esto se puede hacer usando Recursion y Backtracking .
Siga los pasos a continuación para resolver este problema:
- Ordenar la array/vector dado.
- Inicialice una variable global max_length a 0, que almacena el subconjunto de longitud máxima.
- Para cada índice i en la array, llame a la función de recurrencia para encontrar todos los subconjuntos posibles con elementos en el rango [i, N-1] que tengan la suma K .
- Cada vez que se encuentre un subconjunto con suma K , verifique si su tamaño es mayor que el valor max_length actual . En caso afirmativo, actualice el valor de max_length .
- Después de calcular todas las sumas de subconjuntos posibles, devuelve max_length .
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;
// Initialise maximum possible
// length of subsequence
int max_length = 0;
// Store elements to compare
// max_length with its size
// and change the value of
// max_length accordingly
vector<int> store;
// Store the elements of the
// longest subsequence
vector<int> ans;
// Function to find the length
// of longest subsequence
void find_max_length(
vector<int>& arr,
int index, int sum, int k)
{
sum = sum + arr[index];
store.push_back(arr[index]);
if (sum == k) {
if (max_length < store.size()) {
// Update max_length
max_length = store.size();
// Store the subsequence
// elements
ans = store;
}
}
for (int i = index + 1;
i < arr.size(); i++) {
if (sum + arr[i] <= k) {
// Recursively proceed
// with obtained sum
find_max_length(arr, i,
sum, k);
// poping elements
// from back
// of vector store
store.pop_back();
}
// if sum > 0 then we don't
// required thatsubsequence
// so return and continue
// with earlier elements
else
return;
}
return;
}
int longestSubsequence(vector<int> arr,
int n, int k)
{
// Sort the given array
sort(arr.begin(), arr.end());
// Traverse the array
for (int i = 0; i < n; i++) {
// If max_length is already
// greater than or equal
// than remaining length
if (max_length >= n - i)
break;
store.clear();
find_max_length(arr, i, 0, k);
}
return max_length;
}
// Driver code
int main()
{
vector<int> arr{ -3, 0, 1, 1, 2 };
int n = arr.size();
int k = 1;
cout << longestSubsequence(arr,
n, k);
return 0;
}
Java
// Java Program to implement the
// above approach
import java.util.*;
class GFG{
// Initialise maximum possible
// length of subsequence
static int max_length = 0;
// Store elements to compare
// max_length with its size
// and change the value of
// max_length accordingly
static Vector<Integer> store = new Vector<Integer>();
// Store the elements of the
// longest subsequence
static Vector<Integer> ans = new Vector<Integer>();
// Function to find the length
// of longest subsequence
static void find_max_length(
int []arr,
int index, int sum, int k)
{
sum = sum + arr[index];
store.add(arr[index]);
if (sum == k)
{
if (max_length < store.size())
{
// Update max_length
max_length = store.size();
// Store the subsequence
// elements
ans = store;
}
}
for (int i = index + 1;
i < arr.length; i++)
{
if (sum + arr[i] <= k)
{
// Recursively proceed
// with obtained sum
find_max_length(arr, i,
sum, k);
// poping elements
// from back
// of vector store
store.remove(store.size() - 1);
}
// if sum > 0 then we don't
// required thatsubsequence
// so return and continue
// with earlier elements
else
return;
}
return;
}
static int longestSubsequence(int []arr,
int n, int k)
{
// Sort the given array
Arrays.sort(arr);
// Traverse the array
for (int i = 0; i < n; i++)
{
// If max_length is already
// greater than or equal
// than remaining length
if (max_length >= n - i)
break;
store.clear();
find_max_length(arr, i, 0, k);
}
return max_length;
}
// Driver code
public static void main(String[] args)
{
int []arr = { -3, 0, 1, 1, 2 };
int n = arr.length;
int k = 1;
System.out.print(longestSubsequence(arr,
n, k));
}
}
// This code is contributed by Princi Singh
Python3
# Python3 Program to implement the # above approach # Initialise maximum possible # length of subsequence max_length = 0 # Store elements to compare # max_length with its size # and change the value of # max_length accordingly store = [] # Store the elements of the # longest subsequence ans = [] # Function to find the length # of longest subsequence def find_max_length(arr, index, sum, k): global max_length sum = sum + arr[index] store.append(arr[index]) if (sum == k): if (max_length < len(store)): # Update max_length max_length = len(store) # Store the subsequence # elements ans = store for i in range ( index + 1, len(arr)): if (sum + arr[i] <= k): # Recursively proceed # with obtained sum find_max_length(arr, i, sum, k) # poping elements # from back # of vector store store.pop() # if sum > 0 then we don't # required thatsubsequence # so return and continue # with earlier elements else: return return def longestSubsequence(arr, n, k): # Sort the given array arr.sort() # Traverse the array for i in range (n): # If max_length is already # greater than or equal # than remaining length if (max_length >= n - i): break store.clear() find_max_length(arr, i, 0, k) return max_length # Driver code if __name__ == "__main__": arr = [-3, 0, 1, 1, 2] n = len(arr) k = 1 print (longestSubsequence(arr, n, k)) # This code is contributed by Chitranayal
C#
// C# program to implement the
// above approach
using System;
using System.Collections.Generic;
class GFG{
// Initialise maximum possible
// length of subsequence
static int max_length = 0;
// Store elements to compare
// max_length with its size
// and change the value of
// max_length accordingly
static List<int> store = new List<int>();
// Store the elements of the
// longest subsequence
static List<int> ans = new List<int>();
// Function to find the length
// of longest subsequence
static void find_max_length(int []arr,
int index,
int sum, int k)
{
sum = sum + arr[index];
store.Add(arr[index]);
if (sum == k)
{
if (max_length < store.Count)
{
// Update max_length
max_length = store.Count;
// Store the subsequence
// elements
ans = store;
}
}
for(int i = index + 1;
i < arr.Length; i++)
{
if (sum + arr[i] <= k)
{
// Recursively proceed
// with obtained sum
find_max_length(arr, i,
sum, k);
// poping elements
// from back
// of vector store
store.RemoveAt(store.Count - 1);
}
// If sum > 0 then we don't
// required thatsubsequence
// so return and continue
// with earlier elements
else
return;
}
return;
}
static int longestSubsequence(int []arr,
int n, int k)
{
// Sort the given array
Array.Sort(arr);
// Traverse the array
for(int i = 0; i < n; i++)
{
// If max_length is already
// greater than or equal
// than remaining length
if (max_length >= n - i)
break;
store.Clear();
find_max_length(arr, i, 0, k);
}
return max_length;
}
// Driver code
public static void Main(String[] args)
{
int []arr = { -3, 0, 1, 1, 2 };
int n = arr.Length;
int k = 1;
Console.Write(longestSubsequence(arr,
n, k));
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Javascript Program to implement the
// above approach
// Initialise maximum possible
// length of subsequence
let max_length = 0;
// Store elements to compare
// max_length with its size
// and change the value of
// max_length accordingly
let store = [];
// Store the elements of the
// longest subsequence
let ans = [];
// Function to find the length
// of longest subsequence
function find_max_length(arr,index,sum,k)
{
sum = sum + arr[index];
store.push(arr[index]);
if (sum == k)
{
if (max_length < store.length)
{
// Update max_length
max_length = store.length;
// Store the subsequence
// elements
ans = store;
}
}
for (let i = index + 1;
i < arr.length; i++)
{
if (sum + arr[i] <= k)
{
// Recursively proceed
// with obtained sum
find_max_length(arr, i,
sum, k);
// poping elements
// from back
// of vector store
store.pop();
}
// if sum > 0 then we don't
// required thatsubsequence
// so return and continue
// with earlier elements
else
return;
}
return;
}
function longestSubsequence(arr, n, k)
{
// Sort the given array
arr.sort(function(a,b){return a-b;});
// Traverse the array
for (let i = 0; i < n; i++)
{
// If max_length is already
// greater than or equal
// than remaining length
if (max_length >= n - i)
break;
store=[];
find_max_length(arr, i, 0, k);
}
return max_length;
}
// Driver code
let arr = [-3, 0, 1, 1, 2 ];
let n = arr.length;
let k = 1;
document.write(longestSubsequence(arr,n, k));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
5
Complejidad de tiempo: O(N 3 )
Espacio auxiliar: O(N)
Enfoque de programación dinámica: Consulte este artículo para obtener un enfoque más optimizado para resolver el problema.