Module sliding_window 

Siljuvchi oyna (sliding window) texnikasi.

G’oya: ketma-ket elementlardan iborat “oyna” bo’ylab yuramiz. Oynani har safar noldan hisoblash o’rniga, chiqib ketganini ayirib, kirganini qo’shamiz.

 [1, 4, 2, 10, 2, 3, 1, 0, 20]   k = 4
  └────oyna────┘                 yig'indi = 17
     └────oyna────┘              yig'indi = 17 − 1 + 2 = 18

Natijada O(n·k) o’rniga O(n).

Ikki turi bor:

• Qat’iy o’lchamli oyna (max_sum_subarray_k);
• O’zgaruvchan o’lchamli oyna (longest_unique_substring, min_subarray_len).

Functions

longest_unique_substring

Takrorlanuvchi belgisiz eng uzun qism-satr uzunligi.

max_in_windows

Har bir k o’lchamli oynadagi maksimal element (monoton deque bilan).

max_sum_subarray_k

k uzunlikdagi qism-massivning maksimal yig’indisi.

min_subarray_len

Yig’indisi target dan kam bo’lmagan eng qisqa qism-massiv uzunligi.