Dado un arreglo arr[] , la tarea es elegir un subarreglo de tamaño K que contenga el número máximo de puntos de valle con respecto a los elementos adyacentes.
Un elemento arr[i] se conoce como punto valle, si sus dos elementos adyacentes son mayores que él, es decir, 
y .
Ejemplos:
Entrada: arr[] = {5, 4, 6, 4, 5, 2, 3, 1}, K = 7 el
Salida: 3
Explicación:
En subarreglo arr[0-6] = {5, 4, 6, 4, 5, 2, 3}
Hay 3 puntos de valle en el subarreglo, que es el máximo.
Entrada: arr[] = {2, 1, 4, 2, 3, 4, 1, 2}, K = 4
Salida: 1
Explicación:
En subarreglo arr[0-3] = {2, 1, 4, 2}
Solo hay un punto de valle en el subarreglo, que es el máximo.
Planteamiento: La idea es utilizar la técnica de la ventana deslizante para resolver este problema.
A continuación se muestra una ilustración de los pasos del enfoque:
- Encuentre el recuento total de puntos de valle en el primer subarreglo de tamaño K.
- Iterar para todos los puntos iniciales de los posibles subarreglos, es decir, puntos NK del arreglo, y aplicar el principio de inclusión y exclusión para calcular el número de puntos de valle en la ventana actual.
- En cada paso, actualice la respuesta final para calcular el máximo global de cada subarreglo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// maximum number of valley elements
// in the subarrays of size K
#include<bits/stdc++.h>
using namespace std;
// Function to find the valley elements
// in the array which contains
// in the subarrays of the size K
void minpoint(int arr[],int n, int k)
{
int min_point = 0;
for (int i = 1; i < k-1 ; i++)
{
// Increment min_point
// if element at index i
// is smaller than element
// at index i + 1 and i-1
if(arr[i] < arr[i - 1] && arr[i] < arr[i + 1])
min_point += 1;
}
// final_point to maintain maximum
// of min points of subarray
int final_point = min_point;
// Iterate over array
// from kth element
for(int i = k ; i < n; i++)
{
// Leftmost element of subarray
if(arr[i - ( k - 1 )] < arr[i - ( k - 1 ) + 1]&&
arr[i - ( k - 1 )] < arr[i - ( k - 1 ) - 1])
min_point -= 1;
// Rightmost element of subarray
if(arr[i - 1] < arr[i] && arr[i - 1] < arr[i - 2])
min_point += 1;
// if new subarray have greater
// number of min points than previous
// subarray, then final_point is modified
if(min_point > final_point)
final_point = min_point;
}
// Max minimum points in
// subarray of size k
cout<<(final_point);
}
// Driver Code
int main()
{
int arr[] = {2, 1, 4, 2, 3, 4, 1, 2};
int n = sizeof(arr)/sizeof(arr[0]);
int k = 4;
minpoint(arr, n, k);
return 0;
}
// This code contributed by chitranayal
Java
// Java implementation to find the
// maximum number of valley elements
// in the subarrays of size K
class GFG{
// Function to find the valley elements
// in the array which contains
// in the subarrays of the size K
static void minpoint(int arr[], int n, int k)
{
int min_point = 0;
for(int i = 1; i < k - 1; i++)
{
// Increment min_point
// if element at index i
// is smaller than element
// at index i + 1 and i-1
if(arr[i] < arr[i - 1] &&
arr[i] < arr[i + 1])
min_point += 1;
}
// final_point to maintain maximum
// of min points of subarray
int final_point = min_point;
// Iterate over array
// from kth element
for(int i = k ; i < n; i++)
{
// Leftmost element of subarray
if(arr[i - ( k - 1 )] < arr[i - ( k - 1 ) + 1] &&
arr[i - ( k - 1 )] < arr[i - ( k - 1 ) - 1])
min_point -= 1;
// Rightmost element of subarray
if(arr[i - 1] < arr[i] &&
arr[i - 1] < arr[i - 2])
min_point += 1;
// If new subarray have greater
// number of min points than previous
// subarray, then final_point is modified
if(min_point > final_point)
final_point = min_point;
}
// Max minimum points in
// subarray of size k
System.out.println(final_point);
}
// Driver Code
public static void main (String[] args)
{
int arr[] = { 2, 1, 4, 2, 3, 4, 1, 2 };
int n = arr.length;
int k = 4;
minpoint(arr, n, k);
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 implementation to find the # maximum number of valley elements # in the subarrays of size K # Function to find the valley elements # in the array which contains # in the subarrays of the size K def minpoint(arr, n, k): min_point = 0 for i in range(1, k-1): # Increment min_point # if element at index i # is smaller than element # at index i + 1 and i-1 if(arr[i] < arr[i - 1] and arr[i] < arr[i + 1]): min_point += 1 # final_point to maintain maximum # of min points of subarray final_point = min_point # Iterate over array # from kth element for i in range(k, n): # Leftmost element of subarray if(arr[i - ( k - 1 )] < arr[i - ( k - 1 ) + 1] and\ arr[i - ( k - 1 )] < arr[i - ( k - 1 ) - 1]): min_point -= 1 # Rightmost element of subarray if(arr[i - 1] < arr[i] and arr[i - 1] < arr[i - 2]): min_point += 1 # if new subarray have greater # number of min points than previous # subarray, then final_point is modified if(min_point > final_point): final_point = min_point # Max minimum points in # subarray of size k print(final_point) # Driver Code if __name__ == "__main__": arr = [2, 1, 4, 2, 3, 4, 1, 2] n = len(arr) k = 4 minpoint(arr, n, k)
C#
// C# implementation to find the
// maximum number of valley elements
// in the subarrays of size K
using System;
class GFG{
// Function to find the valley elements
// in the array which contains
// in the subarrays of the size K
static void minpoint(int []arr, int n, int k)
{
int min_point = 0;
for(int i = 1; i < k - 1; i++)
{
// Increment min_point
// if element at index i
// is smaller than element
// at index i + 1 and i-1
if(arr[i] < arr[i - 1] &&
arr[i] < arr[i + 1])
min_point += 1;
}
// final_point to maintain maximum
// of min points of subarray
int final_point = min_point;
// Iterate over array
// from kth element
for(int i = k ; i < n; i++)
{
// Leftmost element of subarray
if(arr[i - ( k - 1 )] < arr[i - ( k - 1 ) + 1] &&
arr[i - ( k - 1 )] < arr[i - ( k - 1 ) - 1])
min_point -= 1;
// Rightmost element of subarray
if(arr[i - 1] < arr[i] &&
arr[i - 1] < arr[i - 2])
min_point += 1;
// If new subarray have greater
// number of min points than previous
// subarray, then final_point is modified
if(min_point > final_point)
final_point = min_point;
}
// Max minimum points in
// subarray of size k
Console.WriteLine(final_point);
}
// Driver Code
public static void Main (string[] args)
{
int []arr = { 2, 1, 4, 2, 3, 4, 1, 2 };
int n = arr.Length;
int k = 4;
minpoint(arr, n, k);
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// Javascript implementation to find the
// maximum number of valley elements
// in the subarrays of size K
// Function to find the valley elements
// in the array which contains
// in the subarrays of the size K
function minpoint(arr, n, k) {
let min_point = 0;
for (let i = 1; i < k - 1; i++) {
// Increment min_point
// if element at index i
// is smaller than element
// at index i + 1 and i-1
if (arr[i] < arr[i - 1] && arr[i] < arr[i + 1])
min_point += 1;
}
// final_point to maintain maximum
// of min points of subarray
let final_point = min_point;
// Iterate over array
// from kth element
for (let i = k; i < n; i++) {
// Leftmost element of subarray
if (arr[i - (k - 1)] < arr[i - (k - 1) + 1] &&
arr[i - (k - 1)] < arr[i - (k - 1) - 1])
min_point -= 1;
// Rightmost element of subarray
if (arr[i - 1] < arr[i] && arr[i - 1] < arr[i - 2])
min_point += 1;
// if new subarray have greater
// number of min points than previous
// subarray, then final_point is modified
if (min_point > final_point)
final_point = min_point;
}
// Max minimum points in
// subarray of size k
document.write(final_point);
}
// Driver Code
let arr = [2, 1, 4, 2, 3, 4, 1, 2];
let n = arr.length;
let k = 4;
minpoint(arr, n, k);
// This code contributed by _saurabh_jaiswal
</script>
Producción:
1
Complejidad de tiempo: O(N)