Encuentre el subarreglo de longitud K con pico máximo

Dada una array arr[] de longitud n y un entero positivo K , tenemos que encontrar una subarreglo de longitud K que tenga un pico máximo en su interior. 
Los picos del segmento [l, r] son ​​aquellos índices tales que l < i < r , a[i-1] < a[i] y a[i+1] < a[i] . 
Nota: Los índices de límite l y r para el segmento no son picos. Si hay muchos subarreglos con pico máximo, imprima ese subarreglo cuyo índice izquierdo mínimo.
Ejemplos:
 

Entrada: 
arr = {3, 1, 4, 1, 5, 9, 2, 6}, k = 7 
Salida: 
Izquierda = 1 
Derecha = 7 
Pico = 2 
Explicación: 
Hay dos subarreglo con longitud 7, es decir, [1, 7 ] y [2, 8]. Ambos subarreglos tienen 2 picos en su interior, es decir, 3 y 6 índices son el pico en ambos subarreglos. Tenemos que devolver el subarreglo con l mínimo y pico máximo, es decir, l = 1 y pico = 2.
Entrada: 
arr = {3, 2, 3, 2, 1}, k = 3 
Salida: 
Izquierda = 2 
Derecha = 4 
Pico = 1 
Explicación: 
solo un subarreglo cuya longitud es 3 y el número de picos dentro es 1, es decir, l = 2 y el pico es i = 3. 
 

Enfoque:
El enfoque para resolver este problema es usar una ventana deslizante , donde nos deslizamos a través del tamaño de la ventana de K, y encontramos el recuento total de picos en cada ventana, la ventana que proporcione el número máximo de picos será la respuesta. Mientras movemos el índice derecho, verificamos si un índice agregado es un pico, aumentamos el conteo, y mientras movemos el índice izquierdo, verificamos si el índice eliminado es un pico, si lo es, luego disminuimos el conteo. Tenemos una ventana de tamaño K siempre.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation to Find subarray
// of Length K with Maximum Peak
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the subarray
void findSubArray(int* a, int n, int k)
{
    // Make prefix array to store
    // the prefix sum of peak count
    int pref[n];
 
    pref[0] = 0;
 
    for (int i = 1; i < n - 1; ++i) {
 
        // Count peak for previous index
        pref[i] = pref[i - 1];
 
        // Check if this element is a peak
        if (a[i] > a[i - 1] && a[i] > a[i + 1])
 
            // Increment the count
            pref[i]++;
    }
 
    int peak = 0, left = 0;
 
    for (int i = 0; i + k - 1 < n; ++i)
 
        // Check if number of peak in the sub array
        // whose l = i is greater or not
        if (pref[i + k - 2] - pref[i] > peak) {
            peak = pref[i + k - 2] - pref[i];
            left = i;
        }
 
    // Print the result
    cout << "Left = " << left + 1 << endl;
    cout << "Right = " << left + k << endl;
    cout << "Peak = " << peak << endl;
}
 
// Driver code
int main()
{
    int arr[] = { 3, 2, 3, 2, 1 };
 
    int n = sizeof(arr) / sizeof(arr[0]);
 
    int k = 3;
 
    findSubArray(arr, n, k);
 
    return 0;
}

// Java implementation to Find subarray
// of Length K with Maximum Peak
 
class GFG{
  
// Function to find the subarray
static void findSubArray(int []a, int n, int k)
{
    // Make prefix array to store
    // the prefix sum of peak count
    int []pref = new int[n];
  
    pref[0] = 0;
  
    for (int i = 1; i < n - 1; ++i) {
  
        // Count peak for previous index
        pref[i] = pref[i - 1];
  
        // Check if this element is a peak
        if (a[i] > a[i - 1] && a[i] > a[i + 1])
  
            // Increment the count
            pref[i]++;
    }
  
    int peak = 0, left = 0;
  
    for (int i = 0; i + k - 1 < n; ++i)
  
        // Check if number of peak in the sub array
        // whose l = i is greater or not
        if (pref[i + k - 2] - pref[i] > peak) {
            peak = pref[i + k - 2] - pref[i];
            left = i;
        }
  
    // Print the result
    System.out.print("Left = " +  (left + 1) +"\n");
    System.out.print("Right = " +  (left + k) +"\n");
    System.out.print("Peak = " +  peak +"\n");
}
  
// Driver code
public static void main(String[] args)
{
    int arr[] = { 3, 2, 3, 2, 1 };
  
    int n = arr.length;
  
    int k = 3;
  
    findSubArray(arr, n, k);
  
}
}
 
// This code contributed by Princi Singh

# Python3 implementation to Find subarray
# of Length K with Maximum Peak
 
# Function to find the subarray
def findSubArray(a, n, k):
 
    # Make prefix array to store
    # the prefix sum of peak count
    pref = [0 for i in range(n)]
 
    pref[0] = 0
 
    for i in range(1, n - 1, 1):
        # Count peak for previous index
        pref[i] = pref[i - 1]
 
        # Check if this element is a peak
        if (a[i] > a[i - 1] and a[i] > a[i + 1]):
            # Increment the count
            pref[i] += 1
 
    peak = 0
    left = 0
 
    for i in range(0, n - k + 1, 1):
 
        # Check if number of peak in the sub array
        # whose l = i is greater or not
        if (pref[i + k - 2] - pref[i] > peak):
            peak = pref[i + k - 2] - pref[i]
            left = i
 
    # Print the result
    print("Left =",left + 1)
    print("Right =",left + k)
    print("Peak =",peak)
 
# Driver code
if __name__ == '__main__':
    arr = [3, 2, 3, 2, 1]
 
    n = len(arr)
    k = 3
    findSubArray(arr, n, k)
 
# This code is contributed by Surendra_Gangwar

// C# implementation to Find subarray
// of Length K with Maximum Peak
using System;
 
class GFG{
 
// Function to find the subarray
static void findSubArray(int []a, int n, int k)
{
     
    // Make prefix array to store
    // the prefix sum of peak count
    int []pref = new int[n];
     
    pref[0] = 0;
 
    for(int i = 1; i < n - 1; ++i)
    {
         
       // Count peak for previous index
       pref[i] = pref[i - 1];
        
       // Check if this element is a peak
       if (a[i] > a[i - 1] && a[i] > a[i + 1])
       {
           // Increment the count
           pref[i]++;
       }
    }
 
    int peak = 0;
    int left = 0;
     
    for(int i = 0; i + k - 1 < n; ++i)
    {
         
       // Check if number of peak in the sub array
       // whose l = i is greater or not
       if (pref[i + k - 2] - pref[i] > peak)
       {
           peak = pref[i + k - 2] - pref[i];
           left = i;
       }
    }
        
    // Print the result
    Console.Write("Left = " + (left + 1) + "\n");
    Console.Write("Right = " + (left + k) + "\n");
    Console.Write("Peak = " + peak + "\n");
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr = { 3, 2, 3, 2, 1 };
    int n = arr.Length;
    int k = 3;
 
    findSubArray(arr, n, k);
}
}
 
// This code is contributed by Rohit_ranjan

<script>
// Javascript implementation to Find subarray
// of Length K with Maximum Peak
 
// Function to find the subarray
function findSubArray(a, n, k)
{
 
    // Make prefix array to store
    // the prefix sum of peak count
    let pref = new Array(n);
 
    pref[0] = 0;
 
    for (let i = 1; i < n - 1; ++i)
    {
 
        // Count peak for previous index
        pref[i] = pref[i - 1];
 
        // Check if this element is a peak
        if (a[i] > a[i - 1] && a[i] > a[i + 1])
 
            // Increment the count
            pref[i]++;
    }
 
    let peak = 0, left = 0;
 
    for (let i = 0; i + k - 1 < n; ++i)
 
        // Check if number of peak in the sub array
        // whose l = i is greater or not
        if (pref[i + k - 2] - pref[i] > peak) {
            peak = pref[i + k - 2] - pref[i];
            left = i;
        }
 
    // Print the result
    document.write("Left = " + (left + 1) + "<br>");
    document.write("Right = " + (left + k) + "<br>");
    document.write("Peak = " + peak + "<br>");
}
 
// Driver code
let arr = [3, 2, 3, 2, 1];
let n = arr.length;
let k = 3;
 
findSubArray(arr, n, k);
 
// This code is contributed by gfgking
</script>

Left = 2
Right = 4
Peak = 1

Complejidad de tiempo: O(N)