Cuente los elementos máximos de una array cuya diferencia absoluta no exceda K

Dada una array A y un entero positivo K . La tarea es encontrar el número máximo de elementos para los cuales la diferencia absoluta de cualquiera del par no exceda K .
Ejemplos: 
 

Entrada: A[] = {1, 26, 17, 12, 15, 2}, K = 5 
Salida: 3 
Hay un máximo de 3 valores para que la diferencia absoluta de cada par 
no exceda K(K=5), es decir. , {12, 15, 17}
Entrada: A[] = {1, 2, 5, 10, 8, 3}, K = 4 
Salida: 4 
Hay máximo 4 valores para que la diferencia absoluta de cada par 
no exceda K(K=4) es decir, {1, 2, 3, 5} 
 

Acercarse: 
 

1. Ordene la array dada en orden ascendente.
2. Iterar desde el índice i = 0 hasta n.
3. Para cada A[i] cuente cuántos valores están en el rango A[i] a A[i] + K 
   , es decir, A[i]<= A[j] <= A[i]+K
4. Recuento máximo de devolución

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

// C++ implementation of the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the maximum elements
// in which absolute difference of any pair
// does not exceed K
int maxCount(int A[], int N, int K)
{
    int maximum = 0;
    int i = 0, j = 0;
    int start = 0;
    int end = 0;
 
    // Sort the Given array
    sort(A, A + N);
 
    // Find max elements
    for (i = 0; i < N; i++) {
 
        // Count all elements which are in range
        // A[i] to A[i] + K
        while (j < N && A[j] <= A[i] + K)
            j++;
        if (maximum < (j - i)) {
            maximum = (j - i);
            start = i;
            end = j;
        }
    }
 
    // Return the max count
    return maximum;
}
 
// Driver code
int main()
{
    int A[] = { 1, 26, 17, 12, 15, 2 };
    int N = sizeof(A) / sizeof(A[0]);
    int K = 5;
    cout << maxCount(A, N, K);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
     
// Function to return the maximum elements
// in which absolute difference of any pair
// does not exceed K
static int maxCount(int A[], int N, int K)
{
    int maximum = 0;
    int i = 0, j = 0;
    int start = 0;
    int end = 0;
 
    // Sort the Given array
    Arrays.sort(A);
 
    // Find max elements
    for (i = 0; i < N; i++)
    {
 
        // Count all elements which are in range
        // A[i] to A[i] + K
        while (j < N && A[j] <= A[i] + K)
            j++;
        if (maximum < (j - i))
        {
            maximum = (j - i);
            start = i;
            end = j;
        }
    }
 
    // Return the max count
    return maximum;
}
 
// Driver code
public static void main(String[] args)
{
    int A[] = { 1, 26, 17, 12, 15, 2 };
    int N = A.length;
    int K = 5;
    System.out.println(maxCount(A, N, K));
}
}
 
// This code has been contributed by 29AjayKumar

# Python3 implementation of the approach
 
def maxCount(A, N, K):
 
    maximum = 0
    start = 0
    end = 0
    j = 0
     
    # Sort the Array
    A.sort()
     
    # Find max elements
    for i in range(0, N):
        while(j < N and A[j] <= A[i] + K):
            j += 1
        if maximum < (j - i ):
            maximum = (j - i)
            start = i;
            end = j;
 
    # Return the maximum
    return maximum
 
# Driver code
A = [1, 26, 17, 12, 15, 2]
N = len(A)
K = 5
 
print(maxCount(A, N, K))

// C# implementation of the approach
using System;
 
class GFG
{
     
// Function to return the maximum elements
// in which absolute difference of any pair
// does not exceed K
static int maxCount(int []A, int N, int K)
{
    int maximum = 0;
    int i = 0, j = 0;
    int start = 0;
    int end = 0;
 
    // Sort the Given array
    Array.Sort(A);
 
    // Find max elements
    for (i = 0; i < N; i++)
    {
 
        // Count all elements which are in range
        // A[i] to A[i] + K
        while (j < N && A[j] <= A[i] + K)
            j++;
        if (maximum < (j - i))
        {
            maximum = (j - i);
            start = i;
            end = j;
        }
    }
 
    // Return the max count
    return maximum;
}
 
// Driver code
public static void Main()
{
    int []A = { 1, 26, 17, 12, 15, 2 };
    int N = A.Length;
    int K = 5;
    Console.Write(maxCount(A, N, K));
}
}
 
/* This code contributed by PrinciRaj1992 */

<?php
// PHP implementation of the above approach
 
// Function to return the maximum
// elements in which absolute difference
// of any pair does not exceed K
function maxCount($A, $N, $K)
{
    $maximum = 0;
    $i = 0;
    $j = 0;
    $start = 0;
    $end = 0;
 
    // Sort the Given array
    sort($A);
 
    // Find max elements
    for ($i = 0; $i < $N; $i++)
    {
 
        // Count all elements which
        // are in range A[i] to A[i] + K
        while ($j < $N &&
               $A[$j] <= $A[$i] + $K)
            $j++;
        if ($maximum < ($j - $i))
        {
            $maximum = ($j - $i);
            $start = $i;
            $end = $j;
        }
    }
 
    // Return the max count
    return $maximum;
}
 
// Driver code
$A = array( 1, 26, 17, 12, 15, 2 );
$N = Count($A);
$K = 5;
echo maxCount($A, $N, $K);
 
// This code is contributed
// by Arnab Kundu
?>

<script>
 
// JavaScript implementation of the above approach
 
// Function to return the maximum elements
// in which absolute difference of any pair
// does not exceed K
function maxCount(A, N, K)
{
    var maximum = 0;
    var i = 0, j = 0;
    var start = 0;
    var end = 0;
 
    // Sort the Given array
    A.sort((a,b)=> a-b)
 
    // Find max elements
    for (i = 0; i < N; i++) {
 
        // Count all elements which are in range
        // A[i] to A[i] + K
        while (j < N && A[j] <= A[i] + K)
            j++;
        if (maximum < (j - i)) {
            maximum = (j - i);
            start = i;
            end = j;
        }
    }
 
    // Return the max count
    return maximum;
}
 
// Driver code
var A = [1, 26, 17, 12, 15, 2 ];
var N = A.length;
var K = 5;
document.write( maxCount(A, N, K));
 
 
</script>

3

Complejidad de tiempo: O(N logN), donde N*logN es el tiempo requerido para ordenar la array dada
Espacio auxiliar: O(1), no se requiere espacio adicional