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>
Producción:
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