Dada una array arr[] de longitud N , la tarea es encontrar la longitud de la subsecuencia más larga tal que la diferencia de su elemento máximo y elemento mínimo no sea más que un número entero K.
Una secuencia a es una subsecuencia de una secuencia b si ????a se puede obtener de b mediante la eliminación de varios (posiblemente, cero) elementos. Por ejemplo, [3,1][3,1] es una subsecuencia de [3,2,1][3,2,1] y [4,3,1][4,3,1], pero no una subsecuencia de [1,3,3,7][1,3,3,7] y [3,10,4][3,10,4].
Ejemplos:
Entrada: K = 3, arr[]= {1, 4, 5, 6, 9}
Salida: 3
Explicación:
el subarreglo más grande es {4, 5, 6}Entrada: K = 4, arr[]= {1, 2, 3, 4, 5}
Salida: 5
Explicación:
el subarreglo más grande es {1, 2, 3, 4, 5}
Enfoque ingenuo:
- Genere todos los subarreglos y encuentre el mínimo y el máximo en el subarreglo.
- Calcule la diferencia entre el mínimo y el máximo y, si es menor o igual a K, actualice la respuesta.
Complejidad temporal: O(N 3 )
Enfoque eficiente: la idea es ordenar primero la array y luego usar la búsqueda binaria para optimizar el enfoque.
- Ordenar la array dada
- Para cada elemento distinto A[i] en la array, encuentre el primer elemento A[j] tal que (A[j]-A[i]) > K .
- Para su implementación usamos búsqueda binaria o lower_bound y actualizamos ans cada vez como máximo de ans anteriores y diferencia de índices.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find longest
// subarray such that difference
// of max and min is at-most K
#include <bits/stdc++.h>
using namespace std;
// Function to calculate longest
// subarray with above condition
int findLargestSubarray(
vector<int>& arr,
int N, int K)
{
// Sort the array
sort(arr.begin(), arr.end());
int value1 = arr[0], value2 = 0;
int index1, index2, i, MAX;
index1 = index2 = 0;
i = 0, MAX = 0;
// Loop which will terminate
// when no further elements
// can be included in the subarray
while (index2 != N) {
// first value such that
// arr[index2] - arr[index1] > K
value2 = value1 + (K + 1);
// calculate its index using lower_bound
index2 = lower_bound(arr.begin(),
arr.end(), value2)
- arr.begin();
// index2- index1 will give
// the accurate length
// of subarray then compare
// for MAX length and store
// in MAX variable
MAX = max(MAX, (index2 - index1));
// change the index1
// to next greater element
// than previous one
// and recalculate the value1
index1
= lower_bound(
arr.begin(),
arr.end(), arr[index1] + 1)
- arr.begin();
value1 = arr[index1];
}
// finally return answer MAX
return MAX;
}
// Driver Code
int main()
{
int N, K;
N = 18;
K = 5;
vector<int> arr{ 1, 1, 1, 2, 2,
2, 2, 2, 3,
3, 3, 6, 6, 7,
7, 7, 7, 7 };
cout << findLargestSubarray(arr, N, K);
return 0;
}
15
Complejidad de tiempo: O(N*log(N))
Publicación traducida automáticamente
Artículo escrito por abhijeet010304 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA