Dada una array de enteros arr[] de tamaño N y un entero K . La tarea es encontrar la longitud de la subsecuencia más larga cuya suma sea menor o igual a K .
Ejemplo:
Entrada: arr[] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15} K = 40
Salida: 5
Explicación:
Si seleccionamos subsecuencia {0, 1, 3, 7, 15} entonces la suma total será 26 , que es menor que 40 . Por lo tanto, la longitud de subsecuencia creciente más larga posible es 5 .Entrada: arr[] = {5, 8, 3, 7, 9, 1} K = 4
Salida: 1
Acercarse:
- El problema anterior se puede resolver mediante recursividad.
- Elija el elemento en esa posición si la suma total es menor que K y explore los demás elementos.
- Deje el elemento en esa posición y explore el resto.
La relación de recurrencia se dará como:
Relación de recurrencia:
T(N) = max(solve(arr, N, arr[i], i+1, K-arr[i])+1, solve(arr, N, prevele, i+1, K)) ;
Condiciones base: if(i >= N || K <= 0) devuelve 0
Aquí está la implementación del enfoque anterior:
C++
// C++ program to find the Longest // Increasing Subsequence having sum // value atmost K #include <bits/stdc++.h> using namespace std; int solve(int arr[], int N, int prevele, int i, int K) { // check for base cases if (i >= N || K <= 0) return 0; // check if it is possible to take // current elements if (arr[i] <= prevele || (K - arr[i] < 0)) { return solve(arr, N, prevele, i + 1, K); } // if current element is ignored else { int ans = max( solve(arr, N, arr[i], i + 1, K - arr[i]) + 1, solve(arr, N, prevele, i + 1, K)); return ans; } } // Driver Code int main() { int N = 16; int arr[N] = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 }; int K = 40; cout << solve(arr, N, INT_MIN, 0, K) << endl; }
Java
// Java program to find the Longest // Increasing Subsequence having sum // value atmost K import java.io.*; class GFG{ static int solve(int arr[], int N, int prevele, int i, int K) { // Check for base cases if (i >= N || K <= 0) return 0; // Check if it is possible to take // current elements if (arr[i] <= prevele || (K - arr[i] < 0)) { return solve(arr, N, prevele, i + 1, K); } // If current element is ignored else { int ans = Math.max(solve(arr, N, arr[i], i + 1, K - arr[i]) + 1, solve(arr, N, prevele, i + 1, K)); return ans; } } // Driver code public static void main (String[] args) { int N = 16; int arr[] = new int[]{ 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 }; int K = 40; System.out.print(solve(arr, N, Integer.MIN_VALUE, 0, K)); } } // This code is contributed by Pratima Pandey
Python3
# Python3 program to find the Longest # Increasing Subsequence having sum # value atmost K import sys def solve(arr, N, prevele, i, K): # Check for base cases if (i >= N or K <= 0): return 0; # Check if it is possible to take # current elements if (arr[i] <= prevele or (K - arr[i] < 0)): return solve(arr, N, prevele, i + 1, K); # If current element is ignored else: ans = max(solve(arr, N, arr[i], i + 1, K - arr[i]) + 1, solve(arr, N, prevele, i + 1, K)); return ans; # Driver code if __name__ == '__main__': N = 16; arr = [ 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 ]; K = 40; print(solve(arr, N, -sys.maxsize, 0, K)); # This code is contributed by 29AjayKumar
C#
// C# program to find the Longest // Increasing Subsequence having sum // value atmost K using System; class GFG{ static int solve(int[] arr, int N, int prevele, int i, int K) { // Check for base cases if (i >= N || K <= 0) return 0; // Check if it is possible to take // current elements if (arr[i] <= prevele || (K - arr[i] < 0)) { return solve(arr, N, prevele, i + 1, K); } // If current element is ignored else { int ans = Math.Max(solve(arr, N, arr[i], i + 1, K - arr[i]) + 1, solve(arr, N, prevele, i + 1, K)); return ans; } } // Driver code public static void Main () { int N = 16; int[] arr = new int[]{ 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 }; int K = 40; Console.Write(solve(arr, N, Int32.MinValue, 0, K)); } } // This code is contributed by sanjoy_62
Javascript
<script> // Javascript program to find the Longest // Increasing Subsequence having sum // value atmost K function solve(arr, N, prevele, i, K) { // check for base cases if (i >= N || K <= 0) return 0; // check if it is possible to take // current elements if (arr[i] <= prevele || (K - arr[i] < 0)) { return solve(arr, N, prevele, i + 1, K); } // if current element is ignored else { var ans = Math.max( solve(arr, N, arr[i], i + 1, K - arr[i]) + 1, solve(arr, N, prevele, i + 1, K)); return ans; } } // Driver Code var N = 16; var arr = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]; var K = 40; document.write( solve(arr, N, -1000000000, 0, K)); </script>
5
Tiempo Complejidad: O (2 N )
Espacio Auxiliar: O (1)
Publicación traducida automáticamente
Artículo escrito por sunilkannur98 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA