Техника скольжения окон

31.12.2019Массивы, Технический Scripter

Этот метод показывает, как вложенный цикл for в нескольких задачах может быть преобразован в одиночный цикл for, что снижает сложность времени.

Давайте начнем с задачи для иллюстрации, где мы можем применить эту технику —

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.

Итак, давайте проанализируем проблему с помощью подхода грубой силы . Мы начинаем с первого индекса и суммируем до k-го элемента. Мы делаем это для всех возможных последовательных блоков или групп из k элементов. Этот метод требует вложенного цикла for, внешний цикл for начинается с начального элемента блока из k элементов, а внутренний или вложенный цикл будет складываться до k-го элемента.

Рассмотрим следующую реализацию:

C ++

// O (n * k) решение для поиска максимальной суммы
// подрешетка размера k
#include <iostream>

using namespace std;

// Возвращает максимальную сумму в подмассиве размера k.

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

{

// Инициализировать результат

int max_sum = INT_MIN;

// Рассмотрим все блоки, начинающиеся с i.

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 здесь
// O (n * k) решение для поиска
// максимальная сумма подмассива
// размера k

class GFG {

// Возвращает максимальную сумму в

// подрешетка размера k.

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

{

// Инициализировать результат

int max_sum = Integer.MIN_VALUE;

// Рассмотрим все блоки, начинающиеся с i.

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

}

// Этот код добавлен
// Прерной Сайни.

python3

# O (n * k) решение для поиска
# максимальная сумма подмассива размера k

import sys

INT_MIN = -sys.maxsize -1

# Возвращает максимальную сумму в
# подрешетка размера k.

def maxSum(arr, n, k):

# Инициализировать результат

max_sum = INT_MIN ;

# Рассмотрим все блоки

# начиная с i.

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

# Этот код предоставлен mits

C #

// C # код здесь O (n * k) решение для
// найти максимальную сумму подмассива
// размера k

using System;

class GFG {

// Возвращает максимальную сумму в

// подрешетка размера k.

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

}

// Этот код предоставлен anuj_67.

PHP

<?php
// O (n * k) решение для поиска максимальной суммы
// подрешетка размера k

// Возвращает максимальную сумму в подмассиве размера k.

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

{

// Инициализировать результат

$max_sum = PHP_INT_MIN ;

// Рассмотрим все блоки

// начиная с i.

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

// Этот код предоставлен anuj_67.
?>

Выход :

Из приведенного выше кода можно заметить, что сложность по времени составляет O (k * n), поскольку она содержит два вложенных цикла.

Техника скольжения окон

Технику лучше всего понять с оконным стеклом в шине, рассмотрим окно длиной n и фиксированное в нем окно длины k . Предположим, что изначально панель находится в крайнем левом углу, т.е. в 0 единицах слева. Теперь сопоставьте окно с массивом arr [] размера n и область с current_sum размером k элементов. Теперь, если мы применим силу к окну так, чтобы оно сдвигалось на единицу расстояния вперед. Панель будет охватывать следующие k последовательных элементов.

Рассмотрим массив arr [] = {5, 2, -1, 0, 3} и значение k = 3 и n = 5

Применение техники раздвижных окон :

Мы вычисляем сумму первых k элементов из n членов, используя линейный цикл, и сохраняем сумму в переменной window_sum.
Затем мы будем линейно пастись по массиву, пока он не достигнет конца, и одновременно будем отслеживать максимальную сумму.
Чтобы получить текущую сумму блока из k элементов, просто вычтите первый элемент из предыдущего блока и добавьте последний элемент текущего блока.

Представленное ниже представление прояснит, как окно скользит по массиву.

Это начальная фаза, где мы вычислили начальную сумму окна, начиная с индекса 0. На данном этапе сумма окна равна 6. Теперь мы устанавливаем максимум_сумму текущим_окном, т.е. 6.

Теперь мы сдвигаем наше окно на единицу индекса. Следовательно, теперь он сбрасывает 5 из окна и добавляет 0 в окно. Следовательно, мы получим нашу новую сумму окна, вычтя 5 и затем добавив к нему 0. Итак, наша сумма окна теперь становится 1. Теперь мы сравним эту сумму окна с Maximum_sum. Поскольку оно меньше, мы не будем менять максимум_сумму.

Аналогично, теперь еще раз мы скользим нашим окном по индексу единицы и получаем новую сумму окна равной 2. Снова мы проверяем, больше ли эта текущая сумма окна, чем Maximum_sum до сих пор. Еще раз, это меньше, поэтому мы не меняем Maximum_sum.

Следовательно, для указанного выше массива наш максимум_сум равен 6.

код для приведенного выше описания:

C ++

// O (n) решение для нахождения максимальной суммы
// подрешетка размера k
#include <iostream>

using namespace std;

// Возвращает максимальную сумму в подмассиве размера k.

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

{

// n должно быть больше

if (n < k) {

cout << "Invalid";

return -1;

}

// Вычисляем сумму первого окна размера k

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-код для
// O (n) решение для поиска
// максимальная сумма подмассива
// размера k

class GFG {

// Возвращает максимальную сумму в

// подрешетка размера k.

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

{

// n должно быть больше

if (n < k) {

System.out.println("Invalid");

return -1;

}

// Вычисляем сумму первого окна размера k

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

}

// Этот код добавлен
// Прерной Сайни.

python3

# O (n) решение для поиска
# максимальная сумма подмассива размера k

import sys

INT_MIN = -sys.maxsize -1

def maxSum(arr, n, k):

# n должно быть больше k

if not n > k:

print("Invalid")

return -1

# Вычислить сумму первого окна размера k

max_sum = INT_MIN

window_sum = sum([arr[i] for i in range(k)])

# Вычислить суммы оставшихся окон

# удаление первого элемента предыдущего

# окно и добавление последнего элемента

# текущее окно.

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

n = len(arr)

print(maxSum(arr, n, k))

# Этот код предоставлен Kyle McClay

C #

// C # код для O (n) решения для поиска
// максимальная сумма подмассива размера k

using System;

class GFG {

// Возвращает максимальную сумму в

// подрешетка размера k.

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

{

// n должно быть больше

if (n < k) {

Console.WriteLine("Invalid");

return -1;

}

// Вычисляем сумму первого окна размера k

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

}

// Этот код предоставлен anuj_67.

PHP

<?php
// O (n) решение для нахождения максимальной суммы
// подрешетка размера k

// Возвращает максимальную сумму в
// подрешетка размера k.

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

{

// n должно быть больше

if ($n < $k)

{

echo "Invalid";

return -1;

}

// Вычисляем сумму первого

// окно размера k

$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);

// Этот код предоставлен anuj_67
?>

Выход :

Теперь совершенно очевидно, что временная сложность линейна, поскольку мы видим, что в нашем коде выполняется только один цикл. Следовательно, наша временная сложность равна O (n) .

Мы можем использовать эту технику, чтобы найти max / min k-subarray, XOR, product, sum и т. Д. См. Проблемы со скользящим окном для таких задач.

Эта статья предоставлена Kanika Thakral . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Техника скольжения окон

0.00 (0%) 0 votes