El subconjunto más grande que tiene una suma menor que igual a la suma de los índices respectivos

Dada una array arr[] , la tarea es encontrar la longitud del subconjunto más grande con la suma de elementos menor o igual que la suma de sus índices (indexación basada en 1).

Ejemplos:

Entrada: arr[] = {1, 7, 3, 5, 9, 6, 6} 
Salida: 5 
Explicación: 
el subconjunto más grande es {1, 3, 5, 6, 6} 
Suma de índices = 1 + 3 + 4 + 6 + 7 = 21 
Suma de elementos = 1 + 3 + 5 + 6 + 6 = 21

Entrada: arr[] = {4, 1, 6, 7, 8, 2} 
Salida: 3

Enfoque ingenuo: 
el enfoque más simple para resolver el problema es generar todos los subconjuntos posibles y calcular la longitud de los subconjuntos que tienen la suma de elementos menor o igual que la suma de sus índices respectivos. 

Complejidad temporal: O(N*2 ^N ) 
Espacio auxiliar: O(N)

Enfoque eficiente: 
siga los pasos a continuación para resolver el problema: 

• Iterar sobre todos los índices y considerar solo aquellos índices cuyos valores sean mayores o iguales a los valores de los respectivos valores almacenados en ellos.
• Continúe actualizando la suma de las diferencias obtenidas en el paso anterior.
• Para los elementos restantes, almacene sus diferencias con sus respectivos índices. Ordena las diferencias.
• Incluya elementos en el subconjunto uno por uno y reste la diferencia de la suma . Continúe incluyendo hasta que se encuentre un elemento cuya diferencia con su índice exceda la suma restante o hasta que todos los elementos de la array ya hayan sido incluidos.

A continuación se muestra la implementación del enfoque anterior:

// C++ Program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the length
// of the longest subset
int findSubset(int* a, int n)
{
    // Stores the sum of differences
    // between elements and
    // their respective index
    int sum = 0;
 
    // Stores the size of
    // the subset
    int cnt = 0;
 
    vector<int> v;
 
    // Iterate over the array
    for (int i = 1; i <= n; i++) {
 
        // If an element which is
        // smaller than or equal
        // to its index is encountered
        if (a[i - 1] - i <= 0) {
 
            // Increase count and sum
            sum += a[i - 1] - i;
            cnt += 1;
        }
 
        // Store the difference with
        // index of the remaining
        // elements
        else {
            v.push_back(a[i - 1] - i);
        }
    }
 
    // Sort the differences
    // in increasing order
    sort(v.begin(), v.end());
 
    int ptr = 0;
 
    // Include the differences while
    // sum remains positive or
    while (ptr < v.size()
           && sum + v[ptr] <= 0) {
        cnt += 1;
        ptr += 1;
        sum += v[ptr];
    }
 
    // Return the size
    return cnt;
}
 
// Driver Code
int main()
{
    int arr[] = { 4, 1, 6, 7,
                  8, 2 };
 
    int n = sizeof(arr)
            / sizeof(arr[0]);
 
    // Function Calling
    cout << findSubset(arr, n)
         << endl;
}

// Java program to implement
// the above approach
import java.util.*;
class GFG{
     
// Function to find the length
// of the longest subset
public static int findSubset(int[] a, int n)
{
     
    // Stores the sum of differences
    // between elements and
    // their respective index
    int sum = 0;
 
    // Stores the size of
    // the subset
    int cnt = 0;
 
    Vector<Integer> v = new Vector<>();
 
    // Iterate over the array
    for(int i = 1; i <= n; i++)
    {
         
        // If an element which is
        // smaller than or equal
        // to its index is encountered
        if (a[i - 1] - i <= 0)
        {
             
            // Increase count and sum
            sum += a[i - 1] - i;
            cnt += 1;
        }
 
        // Store the difference with
        // index of the remaining
        // elements
        else
        {
            v.add(a[i - 1] - i);
        }
    }
 
    // Sort the differences
    // in increasing order
    Collections.sort(v);
 
    int ptr = 0;
 
    // Include the differences while
    // sum remains positive or
    while (ptr < v.size() &&
           sum + v.get(ptr) <= 0)
    {
        cnt += 1;
        ptr += 1;
        sum += v.get(ptr);
    }
 
    // Return the size
    return cnt;
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 4, 1, 6, 7, 8, 2 };
    int n = arr.length;
 
    // Function Calling
    System.out.println(findSubset(arr, n));
}
}
 
// This code is contributed by divyeshrabadiya07

# Python3 program to implement 
# the above approach
 
# Function to find the length 
# of the longest subset
def findSubset(a, n):
     
    # Stores the sum of differences 
    # between elements and 
    # their respective index 
    sum = 0
   
    # Stores the size of 
    # the subset 
    cnt = 0
   
    v = [] 
   
    # Iterate over the array 
    for i in range(1, n + 1):
         
        # If an element which is 
        # smaller than or equal 
        # to its index is encountered 
        if (a[i - 1] - i <= 0):
             
            # Increase count and sum 
            sum += a[i - 1] - i 
            cnt += 1
     
        # Store the difference with 
        # index of the remaining 
        # elements 
        else:
            v.append(a[i - 1] - i)
             
    # Sort the differences 
    # in increasing order 
    v.sort()
   
    ptr = 0
   
    # Include the differences while 
    # sum remains positive or 
    while (ptr < len(v) and
           sum + v[ptr] <= 0):
        cnt += 1
        ptr += 1 
        sum += v[ptr] 
     
    # Return the size 
    return cnt
 
# Driver code
if __name__=="__main__":
     
    arr = [ 4, 1, 6, 7, 8, 2 ] 
    n = len(arr)
   
    # Function calling 
    print(findSubset(arr, n))
 
# This code is contributed by rutvik_56

// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
 
class GFG{
     
// Function to find the length
// of the longest subset
public static int findSubset(int[] a, int n)
{
     
    // Stores the sum of differences
    // between elements and
    // their respective index
    int sum = 0;
 
    // Stores the size of
    // the subset
    int cnt = 0;
 
    List<int> v = new List<int>();
 
    // Iterate over the array
    for(int i = 1; i <= n; i++)
    {
         
        // If an element which is
        // smaller than or equal
        // to its index is encountered
        if (a[i - 1] - i <= 0)
        {
             
            // Increase count and sum
            sum += a[i - 1] - i;
            cnt += 1;
        }
 
        // Store the difference with
        // index of the remaining
        // elements
        else
        {
            v.Add(a[i - 1] - i);
        }
    }
 
    // Sort the differences
    // in increasing order
    v.Sort();
 
    int ptr = 0;
 
    // Include the differences while
    // sum remains positive or
    while (ptr < v.Count &&
           sum + v[ptr] <= 0)
    {
        cnt += 1;
        ptr += 1;
        sum += v[ptr];
    }
 
    // Return the size
    return cnt;
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr = { 4, 1, 6, 7, 8, 2 };
    int n = arr.Length;
 
    // Function calling
    Console.WriteLine(findSubset(arr, n));
}
}
 
// This code is contributed by amal kumar choubey

<script>
 
// Javascript program for the above approach
 
// Function to find the length
// of the longest subset
function findSubset(a, n)
{
      
    // Stores the sum of differences
    // between elements and
    // their respective index
    let sum = 0;
  
    // Stores the size of
    // the subset
    let cnt = 0;
  
    let v = [];
  
    // Iterate over the array
    for(let i = 1; i <= n; i++)
    {
          
        // If an element which is
        // smaller than or equal
        // to its index is encountered
        if (a[i - 1] - i <= 0)
        {
              
            // Increase count and sum
            sum += a[i - 1] - i;
            cnt += 1;
        }
  
        // Store the difference with
        // index of the remaining
        // elements
        else
        {
            v.push(a[i - 1] - i);
        }
    }
  
    // Sort the differences
    // in increasing order
    v.sort();
  
    let ptr = 0;
  
    // Include the differences while
    // sum remains positive or
    while (ptr < v.length &&
           sum + v[ptr] <= 0)
    {
        cnt += 1;
        ptr += 1;
        sum += v[ptr];
    }
  
    // Return the size
    return cnt;
}
 
// Driver Code
 
    let arr = [ 4, 1, 6, 7, 8, 2 ];
    let n = arr.length;
  
    // Function Calling
    document.write(findSubset(arr, n));
 
</script>

3

Complejidad de tiempo: O(N*log(N)) 
Complejidad de espacio: O(N)