Розбір для Максимальна сума відрізка фіксованої довжини
Памʼятайте, що цей розбір слід використовувати лише коли ви застрягли, і не копіювати код з нього. Будь ласка, поважайте автора задачі та автора розбору.
Надсилання офіційного розвʼязку до того, як ви самі розвʼяжете задачу, є порушенням, за яке можна отримати блокування.
Надсилання офіційного розвʼязку до того, як ви самі розвʼяжете задачу, є порушенням, за яке можна отримати блокування.
Розбір розв'язку
Наївний підхід — обчислювати суму кожного відрізка окремо за ~O(k)~ — дає загальну складність ~O(n \cdot k)~, що може не встигнути за обмежений час при великих ~n~ і ~k~.
Ефективний розв'язок використовує техніку ковзного вікна (sliding window):
- Обчислити суму першого відрізка ~a_1 + a_2 + \ldots + a_k~ звичайним способом.
- Далі для переходу від відрізка, що починається в позиції ~l~, до відрізка, що починається в позиції ~l+1~, достатньо відняти елемент, який виходить з вікна (~a_l~), і додати елемент, який входить у вікно (~a_{l+k}~).
- На кожному кроці оновлювати максимум серед усіх отриманих сум.
Такий підхід дозволяє обчислити суму кожного наступного відрізка за ~O(1)~, тож загальна складність — ~O(n)~ за часом і ~O(1)~ додаткової пам'яті (не рахуючи самого масиву).
Коментарі