Рубрики

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

Этот метод показывает, как вложенный цикл 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.
?>


Выход :

24

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

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

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

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

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

  1. Мы вычисляем сумму первых k элементов из n членов, используя линейный цикл, и сохраняем сумму в переменной window_sum.
  2. Затем мы будем линейно пастись по массиву, пока он не достигнет конца, и одновременно будем отслеживать максимальную сумму.
  3. Чтобы получить текущую сумму блока из 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
?>

Выход :

24

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

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

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

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

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

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

0.00 (0%) 0 votes