Dado un arreglo arr[] y un entero K , la tarea es encontrar el subarreglo de longitud máxima y mínima tal que la diferencia entre los elementos adyacentes sea como máximo K.
Ejemplos:
Entrada: arr[] = {2, 4, 6}, K = 2
Salida: 3, 3
Explicación:
subarreglo de longitud mínima y máxima tal que la diferencia
entre elementos adyacentes es como máximo 3, que es {2, 4, 2}
Entrada: arr[] = {2, 3, 6, 7, 8}, K = 2
Salida: 2, 3
Explicación:
Longitud mínima Subarreglo(2) => {2, 3}
Longitud máxima Subarreglo(3) => { 6, 7, 8}
Enfoque: la idea es atravesar la array , comenzar desde cada elemento y moverse hacia la derecha y hacia la izquierda hasta que la diferencia entre los elementos adyacentes sea menor que K. Finalmente, actualice el subarreglo de longitud máxima y mínima con la longitud actual como se define a continuación –
if (current_length maximum_length) maximum_length = current_length
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the minimum // and maximum length subarray such // that difference between adjacent // elements is atmost K #include <iostream> using namespace std; // Function to find the maximum and // minimum length subarray void findMaxMinSubArray(int arr[], int K, int n) { // Initialise minimum and maximum // size of subarray in worst case int min = n; int max = 0; // Left will scan the size of // possible subarray in left // of selected element int left; // Right will scan the size of // possible subarray in right // of selected element int right; // Temp will store size of group // associated with every element int tmp; // Loop to find size of subarray // for every element of array for (int i = 0; i < n; i++) { tmp = 1; left = i; // Left will move in left direction // and compare difference between // itself and element left to it while (left - 1 >= 0 && abs(arr[left] - arr[left - 1]) <= K) { left--; tmp++; } // right will move in right direction // and compare difference between // itself and element right to it right = i; while (right + 1 <= n - 1 && abs(arr[right] - arr[right + 1]) <= K) { right++; tmp++; } // if subarray of much lesser or much // greater is found than yet // known then update if (min > tmp) min = tmp; if (max < tmp) max = tmp; } // Print minimum and maximum // possible size of subarray cout << min << ", " << max << endl; } // Driver Code int main() { int arr[] = { 1, 2, 5, 6, 7 }; int K = 2; int n = sizeof(arr) / sizeof(arr[0]); // function call to find maximum // and minimum possible sub array findMaxMinSubArray(arr, K, n); return 0; }
Java
// Java program to find the minimum // and maximum length subarray such // that difference between adjacent // elements is atmost K import java.io.*; import java.util.*; class GFG { // Function to find the maximum and // minimum length subarray static void findMaxMinSubArray(int arr[], int K, int n) { // Initialise minimum and maximum // size of subarray in worst case int min = n; int max = 0; // Left will scan the size of // possible subarray in left // of selected element int left; // Right will scan the size of // possible subarray in right // of selected element int right; // Temp will store size of group // associated with every element int tmp; // Loop to find size of subarray // for every element of array for(int i = 0; i < n; i++) { tmp = 1; left = i; // Left will move in left direction // and compare difference between // itself and element left to it while (left - 1 >= 0 && Math.abs(arr[left] - arr[left - 1]) <= K) { left--; tmp++; } // Right will move in right direction // and compare difference between // itself and element right to it right = i; while (right + 1 <= n - 1 && Math.abs(arr[right] - arr[right + 1]) <= K) { right++; tmp++; } // If subarray of much lesser or much // greater is found than yet // known then update if (min > tmp) min = tmp; if (max < tmp) max = tmp; } // Print minimum and maximum // possible size of subarray System.out.print(min); System.out.print(", "); System.out.print(max); } // Driver code public static void main(String[] args) { int arr[] = { 1, 2, 5, 6, 7 }; int K = 2; int n = arr.length; // Function call to find maximum // and minimum possible sub array findMaxMinSubArray(arr, K, n); } } // This code is contributed by coder001
Python3
# Python3 program to find the minimum # and maximum length subarray such # that difference between adjacent # elements is atmost K # Function to find the maximum and # minimum length subarray def findMaxMinSubArray(arr, K, n): # Initialise minimum and maximum # size of subarray in worst case min = n max = 0 # Left will scan the size of # possible subarray in left # of selected element left = 0 # Right will scan the size of # possible subarray in right # of selected element right = n # Temp will store size of group # associated with every element tmp = 0 # Loop to find size of subarray # for every element of array for i in range(0, n): tmp = 1 left = i # Left will move in left direction # and compare difference between # itself and element left to it while (left - 1 >= 0 and abs(arr[left] - arr[left - 1]) <= K): left = left - 1 tmp = tmp + 1 # Right will move in right direction # and compare difference between # itself and element right to it right = i while (right + 1 <= n - 1 and abs(arr[right] - arr[right + 1]) <= K): right = right + 1 tmp = tmp + 1 # If subarray of much lesser or much # greater is found than yet # known then update if (min > tmp): min = tmp if (max < tmp): max = tmp # Print minimum and maximum # possible size of subarray print(min, end = ', ') print(max, end = '\n') # Driver Code arr = [ 1, 2, 5, 6, 7 ] K = 2 n = len(arr) # Function call to find maximum # and minimum possible sub array findMaxMinSubArray(arr, K, n) # This code is contributed by Pratik
C#
// C# program to find the minimum // and maximum length subarray such // that difference between adjacent // elements is atmost K using System; class GFG{ // Function to find the maximum and // minimum length subarray static void findMaxMinSubArray(int[] arr, int K, int n) { // Initialise minimum and maximum // size of subarray in worst case int min = n; int max = 0; // Left will scan the size of // possible subarray in left // of selected element int left; // Right will scan the size of // possible subarray in right // of selected element int right; // Temp will store size of group // associated with every element int tmp; // Loop to find size of subarray // for every element of array for(int i = 0; i < n; i++) { tmp = 1; left = i; // Left will move in left direction // and compare difference between // itself and element left to it while (left - 1 >= 0 && Math.Abs(arr[left] - arr[left - 1]) <= K) { left--; tmp++; } // Right will move in right direction // and compare difference between // itself and element right to it right = i; while (right + 1 <= n - 1 && Math.Abs(arr[right] - arr[right + 1]) <= K) { right++; tmp++; } // If subarray of much lesser or much // greater is found than yet // known then update if (min > tmp) min = tmp; if (max < tmp) max = tmp; } // Print minimum and maximum // possible size of subarray Console.Write(min); Console.Write(", "); Console.Write(max); } // Driver code public static void Main() { int[] arr = { 1, 2, 5, 6, 7 }; int K = 2; int n = arr.Length; // Function call to find maximum // and minimum possible sub array findMaxMinSubArray(arr, K, n); } } // This code is contributed by AbhiThakur
Javascript
<script> // Java Script program to find the minimum // and maximum length subarray such // that difference between adjacent // elements is atmost K // Function to find the maximum and // minimum length subarray function findMaxMinSubArray(arr, k, n) { // Initialise minimum and maximum // size of subarray in worst case let min = n; let max = 0; // Left will scan the size of // possible subarray in left // of selected element let left; // Right will scan the size of // possible subarray in right // of selected element let right; // Temp will store size of group // associated with every element let tmp; // Loop to find size of subarray // for every element of array for(let i = 0; i < n; i++) { tmp = 1; left = i; // Left will move in left direction // and compare difference between // itself and element left to it while (left - 1 >= 0 && Math.abs(arr[left] - arr[left - 1]) <= K) { left--; tmp++; } // Right will move in right direction // and compare difference between // itself and element right to it right = i; while (right + 1 <= n - 1 && Math.abs(arr[right] - arr[right + 1]) <= K) { right++; tmp++; } // If subarray of much lesser or much // greater is found than yet // known then update if (min > tmp) min = tmp; if (max < tmp) max = tmp; } // Print minimum and maximum // possible size of subarray document.write(min); document.write(", "); document.write(max); } // Driver code let arr = [1, 2, 5, 6, 7 ]; let K = 2; let n = arr.length; // Function call to find maximum // and minimum possible sub array findMaxMinSubArray(arr, K, n); // This code is contributed by sravan </script>
2, 3
Publicación traducida automáticamente
Artículo escrito por madarsh986 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA