Dado un arreglo arr[] de N enteros y un entero K , nuestra tarea es encontrar la longitud del subarreglo más largo tal que para todos los pares posibles en el subarreglo la diferencia absoluta entre los elementos sea menor o igual a K.
Ejemplos:
Entrada: arr[] = {2, 4, 5, 5, 5, 3, 1}, K = 0
Salida: 3
Explicación:
El posible subarreglo con diferencia en elementos como 0 es {5, 5, 5} cuya longitud es 3. Por lo tanto, la salida es 3.Entrada: arr[] = {1, 2, 3, 6, 7}, K = 2
Salida: 3
Explicación:
El posible subarreglo con diferencia en elementos como máximo 2 es {1, 2, 3} cuya longitud es 3. Por lo tanto la salida es 3
Enfoque ingenuo:
para resolver el problema mencionado anteriormente, el método ingenuo es utilizar el enfoque de la fuerza bruta, que consiste en generar todos los subarreglo posible del arreglo dado y verificar si la diferencia entre el elemento máximo y mínimo del subarreglo es como máximo K o no. Si es así, actualice la longitud del subarreglo actual con la longitud máxima. Imprime la longitud máxima del subarreglo después de todas las operaciones.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the Longest subarray
// of the given array with absolute difference between
// elements less than or equal to integer K
#include <bits/stdc++.h>
using namespace std;
int computeLongestSubarray(int arr[], int k, int n)
{
// maxLength is 1 because k >= 0,
// a single element, subarray will always
// have absolute difference zero
int maxLength = 1;
// Check for all possible subarrays
for(int i = 0; i < n; i++)
{
// Initialization of minimum &
// maximum of current subarray
int minOfSub = arr[i];
int maxOfSub = arr[i];
for(int j = i + 1; j < n; j++)
{
// Update the values for minimum & maximum
if (arr[j] > maxOfSub)
maxOfSub = arr[j];
if (arr[j] < minOfSub)
minOfSub = arr[j];
// Check if current subarray satisfies
// the given condition
if ((maxOfSub - minOfSub) <= k)
{
int currLength = j - i + 1;
// Update the value for maxLength
if (maxLength < currLength)
maxLength = currLength;
}
}
}
// Return the final result
return maxLength;
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 6, 7 };
int k = 2;
int n = sizeof(arr) / sizeof(arr[0]);
int maxLength = computeLongestSubarray(arr, k, n);
cout << (maxLength);
}
// This code is contributed by chitranayal
Java
// Java implementation to find the Longest subarray
// of the given array with absolute difference between
// elements less than or equal to integer K
class GFG {
public static int computeLongestSubarray(int arr[],
int k)
{
// maxLength is 1 because k >= 0,
// a single element, subarray will always
// have absolute difference zero
int maxLength = 1;
// Check for all possible subarrays
for (int i = 0; i < arr.length; i++) {
// Initialization of minimum &
// maximum of current subarray
int minOfSub = arr[i];
int maxOfSub = arr[i];
for (int j = i + 1; j < arr.length; j++) {
// Update the values for minimum & maximum
if (arr[j] > maxOfSub)
maxOfSub = arr[j];
if (arr[j] < minOfSub)
minOfSub = arr[j];
// Check if current subarray satisfies
// the given condition
if ((maxOfSub - minOfSub) <= k) {
int currLength = j - i + 1;
// Update the value for maxLength
if (maxLength < currLength)
maxLength = currLength;
}
}
}
// Return the final result
return maxLength;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 2, 3, 6, 7 };
int k = 2;
int maxLength = computeLongestSubarray(arr, k);
System.out.println(maxLength);
}
}
Python3
# Python3 implementation to find the # Longest subarray of the given array # with absolute difference between # elements less than or equal to integer K def computeLongestSubarray (arr, k, n): # maxLength is 1 because k >= 0, # a single element, subarray will always # have absolute difference zero maxLength = 1 # Check for all possible subarrays for i in range(n): # Initialization of minimum & # maximum of current subarray minOfSub = arr[i] maxOfSub = arr[i] for j in range(i + 1, n): # Update the values for # minimum & maximum if (arr[j] > maxOfSub): maxOfSub = arr[j] if (arr[j] < minOfSub): minOfSub = arr[j] # Check if current subarray # satisfies the given condition if ((maxOfSub - minOfSub) <= k): currLength = j - i + 1 # Update the value for maxLength if (maxLength < currLength): maxLength = currLength # Return the final result return maxLength # Driver Code if __name__ == '__main__': arr = [ 1, 2, 3, 6, 7 ] k = 2 n = len(arr) maxLength = computeLongestSubarray(arr, k, n) print(maxLength) # This code is contributed by himanshu77
C#
// C# implementation to find the longest subarray
// of the given array with absolute difference between
// elements less than or equal to integer K
using System;
class GFG
{
public static int computelongestSubarray(int []arr,
int k)
{
// maxLength is 1 because k >= 0,
// a single element, subarray will always
// have absolute difference zero
int maxLength = 1;
// Check for all possible subarrays
for (int i = 0; i < arr.Length; i++)
{
// Initialization of minimum &
// maximum of current subarray
int minOfSub = arr[i];
int maxOfSub = arr[i];
for (int j = i + 1; j < arr.Length; j++)
{
// Update the values for minimum & maximum
if (arr[j] > maxOfSub)
maxOfSub = arr[j];
if (arr[j] < minOfSub)
minOfSub = arr[j];
// Check if current subarray satisfies
// the given condition
if ((maxOfSub - minOfSub) <= k)
{
int currLength = j - i + 1;
// Update the value for maxLength
if (maxLength < currLength)
maxLength = currLength;
}
}
}
// Return the readonly result
return maxLength;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 1, 2, 3, 6, 7 };
int k = 2;
int maxLength = computelongestSubarray(arr, k);
Console.WriteLine(maxLength);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript implementation to find the Longest subarray
// of the given array with absolute difference between
// elements less than or equal to integer K
function computeLongestSubarray(arr,k)
{
// maxLength is 1 because k >= 0,
// a single element, subarray will always
// have absolute difference zero
let maxLength = 1;
// Check for all possible subarrays
for (let i = 0; i < arr.length; i++) {
// Initialization of minimum &
// maximum of current subarray
let minOfSub = arr[i];
let maxOfSub = arr[i];
for (let j = i + 1; j < arr.length; j++) {
// Update the values for minimum & maximum
if (arr[j] > maxOfSub)
maxOfSub = arr[j];
if (arr[j] < minOfSub)
minOfSub = arr[j];
// Check if current subarray satisfies
// the given condition
if ((maxOfSub - minOfSub) <= k) {
let currLength = j - i + 1;
// Update the value for maxLength
if (maxLength < currLength)
maxLength = currLength;
}
}
}
// Return the final result
return maxLength;
}
// Driver Code
let arr=[1, 2, 3, 6, 7];
let k = 2;
let maxLength = computeLongestSubarray(arr, k);
document.write(maxLength);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
3
Complejidad temporal: O(n 2 )
Enfoque eficiente:
para optimizar el enfoque anterior, la idea es usar Heap Data Structure . Inicialice un minHeap que almacenará los índices del subarreglo actual de manera que los elementos estén en orden ascendente, donde el más pequeño aparece en la parte superior y un maxHeap que almacenará los índices del subarreglo actual de manera que los elementos estén en orden descendente, donde el elemento más grande aparece en la parte superior. Luego itere sobre toda la array y para cada iteración verifique si:
- Todos los elementos del subarreglo cumplen la condición de maxOfSub-minOfSub <= k , luego comparamos maxLength hasta ahora con la longitud del subarreglo actual y actualizamos maxLength al máximo de maxLength o la longitud del subarreglo actual.
- Si la condición no se cumple, aumente el puntero inicial para el subarreglo en 1 y elimine todos los índices de minHeap y maxHeap que no estén incluidos en el nuevo subarreglo.
- Después de cada iteración, aumentamos la longitud de nuestro subarreglo incrementando el puntero final.
A continuación se muestra la implementación del enfoque anterior:
Java
// Java implementation to find the Longest
// subarray of the given array with absolute
// difference between elements less than or equal
// to integer K using Heaps
import java.util.*;
class GFG {
public static int computeLongestSubarray(int arr[],
int k)
{
// Stores the maximum length subarray so far
int maxLength = 0;
Deque<Integer> maxHeap = new LinkedList<>();
Deque<Integer> minHeap = new LinkedList<>();
// Marks to the beginning and end
// pointer for current subarray
int beg = 0, end = 0;
while (end < arr.length) {
// Stores the current element being
// added to the subarray
int currEl = arr[end];
// Remove indices of all elements smaller
// than or equal to current from maxHeap
while (maxHeap.size() > 0 &&
arr[maxHeap.peekLast()] <= currEl)
maxHeap.removeLast();
// Add current element's index to maxHeap
maxHeap.addLast(end);
// Remove indices of all elements larger
// than or equal to current from minHeap
while (minHeap.size() > 0 &&
arr[minHeap.peekLast()] >= currEl)
minHeap.removeLast();
// Add current element's index to minHeap
minHeap.addLast(end);
// Index of maximum of current subarray
int maxOfSub = arr[maxHeap.peekFirst()];
// Index of minimum of current subarray
int minOfSub = arr[minHeap.peekFirst()];
// check if the largest possible difference
// between a pair of elements <= k
if (maxOfSub - minOfSub <= k) {
// Length of current subarray
int currLength = end - beg + 1;
// Update maxLength
if (maxLength < currLength)
maxLength = currLength;
}
else {
// If current subarray doesn't satisfy
// the condition then remove the starting
// element from subarray that satisfy
// increment the beginning pointer
beg++;
// Remove elements from heaps that
// are not in the subarray anymore
while (minHeap.size() > 0 &&
minHeap.peekFirst() < beg)
minHeap.removeFirst();
while (maxHeap.size() > 0 &&
maxHeap.peekFirst() < beg)
maxHeap.removeFirst();
}
end++;
}
// Return the final answer
return maxLength;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 2, 3, 6, 7 };
int k = 2;
int maxLength = computeLongestSubarray(arr, k);
System.out.println(maxLength);
}
}
Python3
# Python3 implementation to find the Longest # subarray of the given array with absolute # difference between elements less than or equal # to integer K using Heaps from collections import deque def computeLongestSubarray(arr, k): # Stores the maximum length subarray so far maxLength = 0 maxHeap = [] minHeap = [] # Marks to the beginning and end # pointer for current subarray beg = 0 end = 0 while (end < len(arr)): # print(end) # Stores the current element being # added to the subarray currEl = arr[end] # Remove indices of all elements smaller # than or equal to current from maxHeap while (len(maxHeap) > 0 and arr[maxHeap[-1]] <= currEl): del maxHeap[-1] # Add current element's index to maxHeap maxHeap.append(end) # Remove indices of all elements larger # than or equal to current from minHeap while (len(minHeap) > 0 and arr[minHeap[-1]] >= currEl): # print(minHeap[-1]) del minHeap[-1] # Add current element's index to minHeap minHeap.append(end) # Index of maximum of current subarray maxOfSub = arr[maxHeap[0]] # Index of minimum of current subarray minOfSub = arr[minHeap[0]] # check if the largest possible difference # between a pair of elements <= k if (maxOfSub - minOfSub <= k): # Length of current subarray currLength = end - beg + 1 # Update maxLength if (maxLength < currLength): maxLength = currLength else: # If current subarray doesn't satisfy # the condition then remove the starting # element from subarray that satisfy # increment the beginning pointer beg += 1 # Remove elements from heaps that # are not in the subarray anymore while (len(minHeap) > 0 and minHeap[0] < beg): del minHeap[0] while (len(maxHeap) > 0 and maxHeap[0] < beg): del maxHeap[0] end += 1 # Return the final answer return maxLength # Driver code if __name__ == '__main__': arr = [1, 2, 3, 6, 7] k = 2 maxLength = computeLongestSubarray(arr, k) print(maxLength) # This code is contributed by mohit kumar 29
Javascript
<script>
// JavaScript implementation to find the Longest
// subarray of the given array with absolute
// difference between elements less than or equal
// to integer K using Heaps
function computeLongestSubarray(arr,k)
{
// Stores the maximum length subarray so far
let maxLength = 0;
let maxHeap = [];
let minHeap = [];
// Marks to the beginning and end
// pointer for current subarray
let beg = 0, end = 0;
while (end < arr.length) {
// Stores the current element being
// added to the subarray
let currEl = arr[end];
// Remove indices of all elements smaller
// than or equal to current from maxHeap
while (maxHeap.length > 0 &&
arr[maxHeap[maxHeap.length-1]] <= currEl)
maxHeap.pop();
// Add current element's index to maxHeap
maxHeap.push(end);
// Remove indices of all elements larger
// than or equal to current from minHeap
while (minHeap.length > 0 &&
arr[minHeap[minHeap.length-1]] >= currEl)
minHeap.pop();
// Add current element's index to minHeap
minHeap.push(end);
// Index of maximum of current subarray
let maxOfSub = arr[maxHeap[0]];
// Index of minimum of current subarray
let minOfSub = arr[minHeap[0]];
// check if the largest possible difference
// between a pair of elements <= k
if (maxOfSub - minOfSub <= k) {
// Length of current subarray
let currLength = end - beg + 1;
// Update maxLength
if (maxLength < currLength)
maxLength = currLength;
}
else {
// If current subarray doesn't satisfy
// the condition then remove the starting
// element from subarray that satisfy
// increment the beginning pointer
beg++;
// Remove elements from heaps that
// are not in the subarray anymore
while (minHeap.length > 0 &&
minHeap[0] < beg)
minHeap.shift();
while (maxHeap.length > 0 &&
maxHeap[0] < beg)
maxHeap.shift();
}
end++;
}
// Return the final answer
return maxLength;
}
// Driver code
let arr=[ 1, 2, 3, 6, 7 ];
let k = 2;
let maxLength = computeLongestSubarray(arr, k);
document.write(maxLength);
// This code is contributed by rag2127
</script>
Producción:
3
Complejidad de tiempo: O (n) porque cada elemento de la array se agrega y elimina de los montones solo una vez.