Número máximo de conteo de elementos de valle en un subarreglo de tamaño K

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++ 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 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 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# 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

<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>

1

Complejidad de tiempo: O(N)