Subsecuencia creciente más larga que tiene un valor de suma como máximo K

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:
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:  

  1. 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>
Producción: 

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

Deja una respuesta

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