Да вземем пример

Представете си, че имаме следния масив:

Нашата задача:

  • Намерете maxSumна подмасив.
  • Подмасивът може да бъде толкова дълъг, колкото даден maxSize.

Като се има предвид горният масив и maxSize от 2бихме могли да заключим, че [0, 3] е подмасивът с най-голяма сума сред всички останали подмасиви.

Ако трябваше да измислим решение въз основа на начина, по който решихме това току-що, бихме могли:

  • повторете всяка двойка
  • изчислете сумата
  • съхранявайте сумата + елементите, които са произвели тази сума, като двойка ключови стойности в карта.

Това би означавало, че времето, което ще отнеме, е равно на итерацията през всеки елемент от масива или с други думиO(n). Това не изглежда толкова лошо! Проблемът идва, когато разгледаме космическата сложност. Докато създаваме двойки ключови стойности, ние се сблъскваме с линейна пространствена сложност. В този проблем това не изглежда толкова лошо, защото имаме потенциално само 6 чифта, но какво ще стане, ако колекцията може да бъде няколко хиляди или милиони елементи?

По същество ние изчисляваме и съхраняваме неизползваните изчисления. Сблъскваме се с втори проблем. Нашата времева сложност би могла да бъде по-лоша, ако не гледахме само двойки, а по-скоро потребителят можеше да диктува maxSizeна нашия подмасив. Катастрофа, тъй като може да се наложи да вмъкнем друг цикъл в него, за да повторим елементи в основната колекция въз основа на дадения maxSize .

Въведете техниката на плъзгащ се прозорец

Това е техника за динамично програмиранеза решаване на проблеми, когато искаме да намерим подмасив от данни в рамките на по-голяма колекция, която отговаря на някакво условие.

За проблеми с плъзгащи се прозорци, оптималната времева и пространствена сложностса O(n) време и O(1) пространство. В най-лошия случай преглеждаме цялата колекция веднъж и не разпределяме допълнително място в паметта спрямо елементите в колекцията.

Правим това, като създаваме подмножество от данни (нашият прозорец) и след това го разширяваме или свиваме, докато изпълним нашето условие. С други думи, след като намерим нещо по-добро, продължаваме напред и никога повече не мислим за изгубената информация.

Използвайте това, когато видите проблеми, които изискват от вас погледнете подниз или подмасив.

Имайте предвид, че по дефиниция подмножеството е непрекъснато, което означава, че елементите трябва да са съседни един до друг в колекцията.

Прилагане на плъзгащ се прозорец

Нека отново вземем нашия проблем по-горе. Даден е масивът по-долу и даден maxSize = 2 .

Първо, нека да напишем изискванията на бялата дъска:

  • Итерация през колекцията (с поне O(n)време сложност).
  • Вижте само maxSize n елемента. Ако прозорецът е твърде голям, преоразмерете го.
  • Съхранявайте текущата обща сума на итерираните елементи в прозореца като currentSum. След това сравнете с maxSum или най-голямата сума, изчислена досега. Ако по-голямоактуализирайте maxSum .

Очертаването на изискванията ни досега може да изглежда така:

При първата и втората итерация (i = 0иi = 1съответно) Нямаме проблеми и изглежда, че работи според очакванията. Нека да разгледаме третата итерация, където i = 2.

Сблъскахме се с проблем! Ние следим нашата сума, като правим нещо като currentSum += array[i]

В този момент нашето currentSum w/o resizing завършва като 2. Размерът на прозореца нарушава нашето ограничение maxSize и ако не го поправим, може да сравняваме неточно сумите.

Забелязахте ли, че включих индексите на масива под стойностите? Бялата дъска ни помага да видим всички данни, до които имаме достъп, дори тези, които не съхраняваме изрично в променлива! Това е ключът!

Някои неща, които трябва да отбележите:

  • startIndexе нова променлива. Той представлява началния индекс на нашия прозорец. Изчислява се като i — maxSize + 1 .
  • Вижте currentSum. Прозорецът стана твърде голям и нашият currentSum вече е неточен! Трябва да извадим изоставащата стойност 0.

currentSum вече е по-голямо от maxSum. Ще трябва да добавим малко логика, за да актуализираме maxSum. Ще разгледам това в кода по-долу.

Ако повторим това в четвъртата итерация, резултатът ще бъде същият. Сега, след като разбираме основната концепция на техниката на плъзгащия се прозорец, нека я видим в някакъв код!

function findMaxSubArraySum(array, maxSize) {
    //error handling
    if(array.length < maxSize) return `error, array is too short`;
    let startIdx = 0;
    let currentSum = 0;
    let maxSum = 0;
    for(let i = 0; i < array.length; i++) {
        currentSum += array[i];
        if(i < maxSize) {
            maxSum = currentSum;
        } else {
            currentSum -= array[i - maxSize];
            if(currentSum > maxSum) {
                maxSum = currentSum;
                startIdx = i - maxSize + 1;
            }
        }
    }
    return array.slice(startIdx, startIdx + maxSize);
}

Точно както при бялата дъска по-горе, трябва да зададем някои условия, които трябва да бъдат изпълнени за успех (където намираме ново maxSumи условие) и условие където преоразмеряваме прозореца (вижте else statement& вложени if statement).

Най-накрая използваме slice, за да издърпаме прозореца, когато приключим. За да обобщим,

  • времевата сложност е O(n)
  • космическата сложност е O(1)

В заключение

Надявам се, че ви е харесала тази разбивка защо трябва да използваме техниката на плъзгащия се прозорец, начин за визуализирането й с бяла дъска и нейните основи в код. Моля, практикувайте го!

Свързан е Алгоритъмът на Kadane, който ще разгледаме в сравнение с Плъзгащ се прозорецв бъдеща статия. Ако това ви е харесало, моля, харесайте и абонирайте се за повече актуализации на тази поредица и разгледайте другото съдържание в моя носител!