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>
usingnamespacestd;
intmaxSum(intarr[], intn, intk)
{
intmax_sum = INT_MIN;
for(inti = 0; i < n - k + 1; i++) {
intcurrent_sum = 0;
for(intj = 0; j < k; j++)
current_sum = current_sum + arr[i + j];
max_sum = max(current_sum, max_sum);
}
returnmax_sum;
}
intmain()
{
intarr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };
intk = 4;
intn = sizeof(arr) / sizeof(arr[0]);
cout << maxSum(arr, n, k);
return0;
}
Java
classGFG {
staticintmaxSum(intarr[], intn, intk)
{
intmax_sum = Integer.MIN_VALUE;
for(inti = 0; i < n - k + 1; i++) {
intcurrent_sum = 0;
for(intj = 0; j < k; j++)
current_sum = current_sum + arr[i + j];
max_sum = Math.max(current_sum, max_sum);
}
returnmax_sum;
}
publicstaticvoidmain(String[] args)
{
intarr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20};
intk = 4;
intn = arr.length;
System.out.println(maxSum(arr, n, k));
}
}
Pitón
importsys
print"GFG"
INT_MIN =-sys.maxsize -1
defmaxSum(arr, n, k):
max_sum =INT_MIN
fori inrange(n -k +1):
current_sum =0
forj inrange(k):
current_sum =current_sum +arr[i +j]
max_sum =max(current_sum, max_sum)
returnmax_sum
arr =[1, 4, 2, 10, 2,
3, 1, 0, 20]
k =4
n =len(arr)
print(maxSum(arr, n, k))
C#
usingSystem;
classGFG {
staticintmaxSum(int[] arr, intn, intk)
{
intmax_sum = int.MinValue;
for(inti = 0; i < n - k + 1; i++) {
intcurrent_sum = 0;
for(intj = 0; j < k; j++)
current_sum = current_sum + arr[i + j];
max_sum = Math.Max(current_sum, max_sum);
}
returnmax_sum;
}
publicstaticvoidMain()
{
int[] arr = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };
intk = 4;
intn = arr.Length;
Console.WriteLine(maxSum(arr, n, k));
}
}
PHP
<?php
?>
<?php
functionmaxSum($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);
echomaxSum($arr, $n, $k);
?>
Javascript
<script>
functionmaxSum( 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);
}
returnmax_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 :
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.
Luego, rozaremos linealmente sobre la matriz hasta que llegue al final y, simultáneamente, realizaremos un seguimiento de la suma máxima.
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.
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.
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.
código para la descripción anterior:
C ++
#include <iostream>
usingnamespacestd;
intmaxSum(intarr[], intn, intk)
{
if(n < k) {
cout << "Invalid";
return-1;
}
intmax_sum = 0;
for(inti = 0; i < k; i++)
max_sum += arr[i];
intwindow_sum = max_sum;
for(inti = k; i < n; i++) {
window_sum += arr[i] - arr[i - k];
max_sum = max(max_sum, window_sum);
}
returnmax_sum;
}
intmain()
{
intarr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };
intk = 4;
intn = sizeof(arr) / sizeof(arr[0]);
cout << maxSum(arr, n, k);
return0;
}
Java
classGFG {
staticintmaxSum(intarr[], intn, intk)
{
if(n < k) {
System.out.println("Invalid");
return-1;
}
intmax_sum = 0;
for(inti = 0; i < k; i++)
max_sum += arr[i];
intwindow_sum = max_sum;
for(inti = k; i < n; i++) {
window_sum += arr[i] - arr[i - k];
max_sum = Math.max(max_sum, window_sum);
}
returnmax_sum;
}
publicstaticvoidmain(String[] args)
{
intarr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20};
intk = 4;
intn = arr.length;
System.out.println(maxSum(arr, n, k));
}
}
Pitón
defmaxSum(arr, k):
n =len(arr)
ifn < k:
print("Invalid")
return-1
window_sum =sum(arr[:k])
max_sum =window_sum
fori inrange(n -k):
window_sum =window_sum -arr[i] +arr[i +k]
max_sum =max(window_sum, max_sum)
returnmax_sum
arr =[1, 4, 2, 10, 2, 3, 1, 0, 20]
k =4
print(maxSum(arr, k))
C#
usingSystem;
classGFG {
staticintmaxSum(int[] arr, intn, intk)
{
if(n < k) {
Console.WriteLine("Invalid");
return-1;
}
intmax_sum = 0;
for(inti = 0; i < k; i++)
max_sum += arr[i];
intwindow_sum = max_sum;
for(inti = k; i < n; i++) {
window_sum += arr[i] - arr[i - k];
max_sum = Math.Max(max_sum, window_sum);
}
returnmax_sum;
}
publicstaticvoidMain()
{
int[] arr = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };
intk = 4;
intn = arr.Length;
Console.WriteLine(maxSum(arr, n, k));
}
}
PHP
<?php
functionmaxSum( $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);
echomaxSum($arr, $n, $k);
?>
Javascript
functionmaxSumofK(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;
}
}
returnmax;
}
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 …