Saltar al contenido
INSTRUCCIONES

Técnica de deslizamiento de ventana – GeeksforGeeks

septiembre 29, 2021
gfg 200x200 min
Contenidos
1 C ++
2 Java
3 Pitón
4 C#
5 PHP
6 Javascript
7 C ++
8 Java
9 Pitón
10 C#
11 PHP
12 Javascript

Esta técnica muestra cómo un bucle for anidado en algunos problemas se puede convertir en un bucle for único para reducir la complejidad del tiempo.
Comencemos con un problema de ilustración en el que podemos aplicar esta técnica: 

Given an array of integers of size ‘n’.
Our aim is to calculate the maximum sum of ‘k’ 
consecutive elements in the array.

Input  : arr[] = {100, 200, 300, 400}
         k = 2
Output : 700

Input  : arr[] = {1, 4, 2, 10, 23, 3, 1, 0, 20}
         k = 4 
Output : 39
We get maximum sum by adding subarray {4, 2, 10, 23}
of size 4.

Input  : arr[] = {2, 3}
         k = 3
Output : Invalid
There is no subarray of size 3 as size of whole
array is 2.

Entonces, analicemos el problema con Enfoque de fuerza bruta. Comenzamos con el primer índice y sumamos hasta k-ésimo elemento. Lo hacemos para todos los posibles bloques consecutivos o grupos de k elementos. Este método requiere un bucle for anidado, el bucle for externo comienza con el elemento inicial del bloque de k elementos y el bucle interno o anidado se sumará hasta el k-ésimo elemento.

Considere la siguiente implementación:

C ++

#include <bits/stdc++.h>

using namespace std;

int maxSum(int arr[], int n, int k)

{

    

    int max_sum = INT_MIN;

    

    for (int i = 0; i < n - k + 1; i++) {

        int current_sum = 0;

        for (int j = 0; j < k; j++)

            current_sum = current_sum + arr[i + j];

        

        max_sum = max(current_sum, max_sum);

    }

    return max_sum;

}

int main()

{

    int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };

    int k = 4;

    int n = sizeof(arr) / sizeof(arr[0]);

    cout << maxSum(arr, n, k);

    return 0;

}

Java

class GFG {

    

    

    static int maxSum(int arr[], int n, int k)

    {

        

        int max_sum = Integer.MIN_VALUE;

        

        for (int i = 0; i < n - k + 1; i++) {

            int current_sum = 0;

            for (int j = 0; j < k; j++)

                current_sum = current_sum + arr[i + j];

            

            max_sum = Math.max(current_sum, max_sum);

        }

        return max_sum;

    }

    

    public static void main(String[] args)

    {

        int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };

        int k = 4;

        int n = arr.length;

        System.out.println(maxSum(arr, n, k));

    }

}

Pitón

import sys

print "GFG"

INT_MIN = -sys.maxsize - 1

def maxSum(arr, n, k):

    

    max_sum = INT_MIN

    

    

    for i in range(n - k + 1):

        current_sum = 0

        for j in range(k):

            current_sum = current_sum + arr[i + j]

        

        max_sum = max(current_sum, max_sum)

    return max_sum

arr = [1, 4, 2, 10, 2,

       3, 1, 0, 20]

k = 4

n = len(arr)

print(maxSum(arr, n, k))

C#

using System;

class GFG {

    

    

    static int maxSum(int[] arr, int n, int k)

    {

        

        int max_sum = int.MinValue;

        

        

        for (int i = 0; i < n - k + 1; i++) {

            int current_sum = 0;

            for (int j = 0; j < k; j++)

                current_sum = current_sum + arr[i + j];

            

            max_sum = Math.Max(current_sum, max_sum);

        }

        return max_sum;

    }

    

    public static void Main()

    {

        int[] arr = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };

        int k = 4;

        int n = arr.Length;

        Console.WriteLine(maxSum(arr, n, k));

    }

}

PHP

<?php

    

?>

<?php

function maxSum($arr, $n, $k)

{

    

    

    $max_sum = PHP_INT_MIN ;

    

    

    for ( $i = 0; $i < $n - $k + 1; $i++)

    {

        $current_sum = 0;

        for ( $j = 0; $j < $k; $j++)

            $current_sum = $current_sum +

                            $arr[$i + $j];

        

        $max_sum = max($current_sum, $max_sum );

    }

    return $max_sum;

}

    

    $arr = array(1, 4, 2, 10, 2, 3, 1, 0, 20);

    $k = 4;

    $n = count($arr);

    echo maxSum($arr, $n, $k);

?>

Javascript

<script>

function maxSum( arr, n, k){

    

    let max_sum = Number.MIN_VALUE;

    

    for (let i = 0; i < n - k + 1; i++) {

        let current_sum = 0;

        for (let j = 0; j < k; j++)

            current_sum = current_sum + arr[i + j];

        

        max_sum = Math.max(current_sum, max_sum);

    }

    return max_sum;

}

let arr = [ 1, 4, 2, 10, 2, 3, 1, 0, 20 ];

let k = 4;

let n = arr.length;

document.write(maxSum(arr, n, k));

</script>

Se puede observar en el código anterior que la complejidad del tiempo es O (k * n) ya que contiene dos bucles anidados.

Técnica de deslizamiento de ventana

La técnica se puede entender mejor con el cristal de la ventana en el autobús, considere una ventana de longitud norte y el cristal que se fija en él de largo k. Considere, inicialmente el panel está en el extremo izquierdo, es decir, a 0 unidades desde la izquierda. Ahora, co-relacione la ventana con la matriz arr[] de tamaño ny panel con current_sum de tamaño k elementos. Ahora, si aplicamos fuerza en la ventana de manera que se mueva una unidad de distancia hacia adelante. El panel cubrirá a continuación k elementos consecutivos.
Considere una matriz arr[] = {5, 2, -1, 0, 3} y valor de k = 3 y norte = 5
Aplicar la técnica de la ventana deslizante :

  1. Calculamos la suma de los primeros k elementos de n términos usando un ciclo lineal y almacenamos la suma en la variable window_sum.
  2. Luego, rozaremos linealmente sobre la matriz hasta que llegue al final y, simultáneamente, realizaremos un seguimiento de la suma máxima.
  3. Para obtener la suma actual del bloque de k elementos, simplemente reste el primer elemento del bloque anterior y agregue el último elemento del bloque actual.

La siguiente representación dejará en claro cómo se desliza la ventana sobre la matriz.
Esta es la fase inicial en la que hemos calculado la suma de la ventana inicial a partir del índice 0. En esta etapa, la suma de la ventana es 6. Ahora, establecemos la suma_máxima como ventana_actual, es decir, 6.

sliding window1

Ahora, deslizamos nuestra ventana por un índice de unidad. Por lo tanto, ahora descarta 5 de la ventana y agrega 0 a la ventana. Por lo tanto, obtendremos la suma de nuestra nueva ventana restando 5 y luego agregando 0. Entonces, nuestra suma de ventana ahora se convierte en 1. Ahora, compararemos esta suma de ventana con la suma_máxima. Como es más pequeño, no cambiaremos la suma_máxima.

sliding window2

De manera similar, ahora una vez más deslizamos nuestra ventana por un índice unitario y obtenemos que la suma de la nueva ventana sea 2. Nuevamente verificamos si esta suma de la ventana actual es mayor que la suma_máxima hasta ahora. Una vez más, es más pequeño, por lo que no cambiamos la suma_máxima.
Por lo tanto, para la matriz anterior, nuestra suma_máxima es 6.

sliding window3

código para la descripción anterior:

C ++

#include <iostream>

using namespace std;

int maxSum(int arr[], int n, int k)

{

    

    if (n < k) {

        cout << "Invalid";

        return -1;

    }

    

    int max_sum = 0;

    for (int i = 0; i < k; i++)

        max_sum += arr[i];

    

    

    

    

    int window_sum = max_sum;

    for (int i = k; i < n; i++) {

        window_sum += arr[i] - arr[i - k];

        max_sum = max(max_sum, window_sum);

    }

    return max_sum;

}

int main()

{

    int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };

    int k = 4;

    int n = sizeof(arr) / sizeof(arr[0]);

    cout << maxSum(arr, n, k);

    return 0;

}

Java

class GFG {

    

    

    static int maxSum(int arr[], int n, int k)

    {

        

        if (n < k) {

            System.out.println("Invalid");

            return -1;

        }

        

        int max_sum = 0;

        for (int i = 0; i < k; i++)

            max_sum += arr[i];

        

        

        

        

        int window_sum = max_sum;

        for (int i = k; i < n; i++) {

            window_sum += arr[i] - arr[i - k];

            max_sum = Math.max(max_sum, window_sum);

        }

        return max_sum;

    }

    

    public static void main(String[] args)

    {

        int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };

        int k = 4;

        int n = arr.length;

        System.out.println(maxSum(arr, n, k));

    }

}

Pitón

def maxSum(arr, k):

    

    n = len(arr)

    

    if n < k:

        print("Invalid")

        return -1

    

    window_sum = sum(arr[:k])

    

    max_sum = window_sum

    

    

    

    

    for i in range(n - k):

        window_sum = window_sum - arr[i] + arr[i + k]

        max_sum = max(window_sum, max_sum)

    return max_sum

arr = [1, 4, 2, 10, 2, 3, 1, 0, 20]

k = 4

print(maxSum(arr, k))

C#

using System;

class GFG {

    

    

    static int maxSum(int[] arr, int n, int k)

    {

        

        if (n < k) {

            Console.WriteLine("Invalid");

            return -1;

        }

        

        int max_sum = 0;

        for (int i = 0; i < k; i++)

            max_sum += arr[i];

        

        

        

        

        int window_sum = max_sum;

        for (int i = k; i < n; i++) {

            window_sum += arr[i] - arr[i - k];

            max_sum = Math.Max(max_sum, window_sum);

        }

        return max_sum;

    }

    

    public static void Main()

    {

        int[] arr = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };

        int k = 4;

        int n = arr.Length;

        Console.WriteLine(maxSum(arr, n, k));

    }

}

PHP

<?php

function maxSum( $arr, $n, $k)

{

    

    if ($n < $k)

    {

        echo "Invalid";

        return -1;

    }

    

    

    $max_sum = 0;

    for($i = 0; $i < $k; $i++)

    $max_sum += $arr[$i];

    

    

    

    

    $window_sum = $max_sum;

    for ($i = $k; $i < $n; $i++)

    {

        $window_sum += $arr[$i] - $arr[$i - $k];

        $max_sum = max($max_sum, $window_sum);

    }

    return $max_sum;

}

    

    $arr = array(1, 4, 2, 10, 2, 3, 1, 0, 20);

    $k = 4;

    $n = count($arr);

    echo maxSum($arr, $n, $k);

?>

Javascript

function maxSumofK(arr, k) {

let max = 0;

let sum = 0;

for(let n = 0; n <  k ; n++) {

    sum +=  arr[n];      

}

 for(let i = k; i < arr.length; i++) {    

        sum += arr[i] - arr[i-k];

        

           if(sum > max) {

               max = sum;

           }

        }

    return max;

}

let arr = [1, 4, 2, 10, 2, 3, 1, 0, 20 ];

console.log(maxSumofK(arr, 4))

Ahora, es bastante obvio que la complejidad del tiempo es lineal, ya que podemos ver que solo se ejecuta un ciclo en nuestro código. Por lo tanto, nuestra Complejidad de Tiempo es Sobre).
Podemos usar esta técnica para encontrar k-subarreglo máximo / mínimo, XOR, producto, suma, etc. Consulte los problemas de ventanas deslizantes para tales problemas.
https://youtu.be/9-3BXsfrpbY?list=PLqM7alHXFySEQDk2MDfbwEdjd2svVJH9p

Este artículo es una contribución de Kanika Thakral. Si te gusta GeeksforGeeks y te gustaría …

close