1. Идея

Нужно найти максимальную сумму среди всех подряд идущих отрезков длины ровно k.

Перебирать каждый такой отрезок и каждый раз заново суммировать его элементы слишком дорого: один отрезок считается за O(k), а всего таких отрезков порядка n, значит получится до O(nk).

Гораздо лучше использовать метод скользящего окна:

• сначала посчитать сумму первого окна из k элементов;
• потом сдвигать окно вправо на 1:
  • добавить новый элемент, который вошёл в окно;
  • вычесть старый элемент, который из окна вышел.

Так сумма каждого следующего окна считается за O(1).

2. Наблюдения

1. Все подходящие отрезки имеют одинаковую длину k.
2. Если известна сумма окна a[l] + a[l+1] + ... + a[r], где r - l + 1 = k, то сумма следующего окна:
   • a[l+1] + a[l+2] + ... + a[r] + a[r+1]
   • получается из предыдущей суммы так: новая сумма = старая сумма - a[l] + a[r+1]
3. Значения a_i могут быть большими по модулю, а n тоже большое, поэтому сумма может не поместиться в 32-битный тип. Нужен 64-битный целый тип:
   • в C++ это long long;
   • в Python обычный int подходит.

3. Алгоритм

1. Считать n, k и массив a.
2. Посчитать сумму первых k элементов. Это будет сумма первого окна.
3. Сохранить её в переменную answer.
4. Для каждого i от k до n - 1:
   • прибавить a[i] — новый элемент вошёл в окно;
   • вычесть a[i - k] — старый элемент вышел из окна;
   • обновить answer, если новая сумма больше.
5. Вывести answer.

4. Почему это работает

Сначала мы точно считаем сумму первого окна длины k, то есть элементов с индексами от 0 до k - 1.

Дальше на каждом шаге рассматривается следующее окно длины k. Пусть сейчас известно окно: a[i-k], a[i-k+1], ..., a[i-1].

Когда мы переходим к следующему окну: a[i-k+1], a[i-k+2], ..., a[i],

из суммы нужно:

• убрать a[i-k], потому что этот элемент больше не входит в окно;
• добавить a[i], потому что он вошёл в окно.

Значит, переменная current_sum всегда хранит точную сумму текущего окна длины k.

Мы последовательно перебираем все возможные окна длины k и для каждого знаем его сумму. Поэтому, если каждый раз обновлять максимум, в answer окажется максимальная сумма среди всех таких окон.

5. Сложность

• Время: O(n), потому что каждый элемент участвует в вычислениях константное число раз.
• Память: O(n) на хранение массива.

6. Код на C++17

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;

    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    long long current_sum = 0;
    for (int i = 0; i < k; i++) {
        current_sum += a[i];
    }

    long long answer = current_sum;

    for (int i = k; i < n; i++) {
        current_sum += a[i];
        current_sum -= a[i - k];
        if (current_sum > answer) {
            answer = current_sum;
        }
    }

    cout << answer << "\n";
    return 0;
}

7. Код на Python 3

n, k = map(int, input().split())
a = list(map(int, input().split()))

current_sum = sum(a[:k])
answer = current_sum

for i in range(k, n):
    current_sum += a[i] - a[i - k]
    if current_sum > answer:
        answer = current_sum

print(answer)