Subsecuencia más larga con diferencia absoluta de pares como al menos el máximo de Subsecuencia

Dada una array arr[] de longitud N . La tarea es encontrar la longitud de la subsecuencia más larga de la array de modo que la diferencia absoluta entre cualquier par de elementos sea mayor o igual que el elemento máximo en esa subsecuencia.

Ejemplos:

Entrada: N = 6, arr[] = {1, 1, 0, 0, 0, 0}
Salida: 4
Explicación: considerando 0 como el elemento máximo de la subsecuencia, la array más larga se puede hacer 
eligiendo elementos del arr ₃ al arr ₆ => {0, 0, 0, 0}. 
Por lo tanto, Longitud de la subsecuencia anterior = 4.

Entrada: N = 4, arr[] = {-3, 0, 2, 0}
Salida: 3

Planteamiento: La solución al problema se basa en la siguiente observación.

•  Trate de incluir tantos elementos negativos y de valor 0 como sea posible porque en una array de todos los elementos negativos y de valor cero, la diferencia absoluta de dos pares cualesquiera siempre sería mayor o igual a cero y el elemento máximo en esa subsecuencia sería menor que o igual a cero.
• Ahora, el enfoque debe ser agregar solo un elemento positivo si es posible, en la subsecuencia porque al considerar un número de elementos positivos mayor o igual a 2, podría surgir un escenario en el que ambos elementos positivos estarían en consideración como un par y luego su la diferencia absoluta sería menor que el elemento máximo (que sería uno de los elementos positivos tomados).

La observación anterior se puede implementar clasificando la array y encontrando la secuencia más larga que satisfaga la condición dada del enunciado del problema. Siga los pasos a continuación:

• Ordenar array en orden descendente.
• Inicialice la variable de respuesta con un valor igual a N dado .
• Comience a iterar la array y cuente cuántos elementos no se pueden tener en cuenta para una subsecuencia verificando si la diferencia entre cualquier par es mayor o igual que el elemento máximo de esa subsecuencia.
• Retorno (respuesta – recuento de elementos) .

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

// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to get longest subsequence
int solve(int arr[], int n)
{
 
    // Sort the array in descending order
    sort(arr, arr + n, greater<int>());
 
    // Initialize answer variable equal
    // to value of N
    int answer = n;
 
    // Count of elements
    // that wont be included in
    // the longest subsequence
    int j = 0;
 
    // Traversing the array
    for (int i = 0; i < n; i++) {
 
        if (i + 1 < n) {
 
            // Checking using the given condition
            // and taking count of elements
            // not to be included in the answer
            if (abs(arr[i] - arr[i + 1])
                < arr[j]) {
                j++;
            }
        }
    }
 
    // Printing the final answer
    return answer - j;
}
 
// Driver Code
int main()
{
    int N = 4;
    int arr[] = { -3, 0, 2, 0 };
 
    // Function call
    int ans = solve(arr, N);
    cout << ans;
    return 0;
}

// Java code for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG {
 
  // Function to reverse the array
  static void reverse(int a[], int n){
    int i, k, t;
    for (i = 0; i < n / 2; i++) {
      t = a[i];
      a[i] = a[n - i - 1];
      a[n - i - 1] = t;
    }
  }
 
  // Function to get longest subsequence
  static int solve(int arr[], int n)
  {
 
    // Sort the array in descending order
    Arrays.sort(arr);
    //Now reverse the array
    reverse(arr, n);
 
    // Initialize answer variable equal
    // to value of N
    int answer = n;
 
    // Count of elements
    // that wont be included in
    // the longest subsequence
    int j = 0;
 
    // Traversing the array
    for (int i = 0; i < n; i++) {
 
      if (i + 1 < n) {
 
        // Checking using the given condition
        // and taking count of elements
        // not to be included in the answer
        if (Math.abs(arr[i] - arr[i + 1])
            < arr[j]) {
          j++;
        }
      }
    }
 
    // Printing the final answer
    return answer - j;
  }
 
  // Driver Code
  public static void main (String[] args) {
    int N = 4;
    int arr[] = { -3, 0, 2, 0 };
 
    // Function call
    int ans = solve(arr, N);
    System.out.println(ans);
 
  }
}
 
// This code is contributed by hrithikgarg03188.

# Python 3 code for the above approach
 
# Function to get longest subsequence
def solve(arr, n):
 
    # Sort the array in descending order
    arr.sort()
    arr.reverse()
 
    # Initialize answer variable equal
    # to value of N
    answer = n
 
    # Count of elements
    # that wont be included in
    # the longest subsequence
    j = 0
 
    # Traversing the array
    for i in range(n):
 
        if (i + 1 < n):
 
            # Checking using the given condition
            # and taking count of elements
            # not to be included in the answer
            if (abs(arr[i] - arr[i + 1])
                    < arr[j]):
                j += 1
 
    # Printing the final answer
    return answer - j
 
# Driver Code
if __name__ == "__main__":
 
    N = 4
    arr = [-3, 0, 2, 0]
 
    # Function call
    ans = solve(arr, N)
    print(ans)
 
    # This code is contributed by ukasp.

// C# code for the above approach
using System;
class GFG {
 
  // Function to reverse the array
  static void reverse(int[] a, int n)
  {
    int i, k, t;
    for (i = 0; i < n / 2; i++) {
      t = a[i];
      a[i] = a[n - i - 1];
      a[n - i - 1] = t;
    }
  }
 
  // Function to get longest subsequence
  static int solve(int[] arr, int n)
  {
 
    // Sort the array in descending order
    Array.Sort(arr);
 
    // Now reverse the array
    reverse(arr, n);
 
    // Initialize answer variable equal
    // to value of N
    int answer = n;
 
    // Count of elements
    // that wont be included in
    // the longest subsequence
    int j = 0;
 
    // Traversing the array
    for (int i = 0; i < n; i++) {
 
      if (i + 1 < n) {
 
        // Checking using the given condition
        // and taking count of elements
        // not to be included in the answer
        if (Math.Abs(arr[i] - arr[i + 1])
            < arr[j]) {
          j++;
        }
      }
    }
 
    // Printing the final answer
    return answer - j;
  }
 
  // Driver Code
  public static void Main()
  {
    int N = 4;
    int[] arr = { -3, 0, 2, 0 };
 
    // Function call
    int ans = solve(arr, N);
    Console.WriteLine(ans);
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
       // JavaScript code for the above approach
 
       // Function to get longest subsequence
       function solve(arr, n) {
 
           // Sort the array in descending order
           arr.sort(function (a, b) { return b - a })
 
           // Initialize answer variable equal
           // to value of N
           let answer = n;
 
           // Count of elements
           // that wont be included in
           // the longest subsequence
           let j = 0;
 
           // Traversing the array
           for (let i = 0; i < n; i++) {
 
               if (i + 1 < n) {
 
                   // Checking using the given condition
                   // and taking count of elements
                   // not to be included in the answer
                   if (Math.abs(arr[i] - arr[i + 1])
                       < arr[j]) {
                       j++;
                   }
               }
           }
 
           // Printing the final answer
           return answer - j;
       }
 
       // Driver Code
 
       let N = 4;
       let arr = [-3, 0, 2, 0];
 
       // Function call
       let ans = solve(arr, N);
       document.write(ans);
 
 
    // This code is contributed by Potta Lokesh
   </script>

3

Complejidad de tiempo: O(N*logN)
Espacio auxiliar: O(1)