Gọi ~S[i]~ là mảng cộng dồn của dãy ~A~.Ta có tổng của đoạn ~[l,r]~ là ~sum(l,r) = S[r] - S[l-1]~

Ta cần chọn ra hai đoạn ~[x,y]~ và ~[u,v]~ sao cho ~y = x + k - 1; v = u + k -1~ và ~y < u~, đồng thời ~|sum(x,y)-sum(u,v)|~ đạt ~max~.

Ta sẽ duyệt từng đoạn ~[u,v]~ trước, để ~|sum(x,y)-sum(u,v)|~ đạt ~max~, ta cần ~sum(x,y)~ bé nhất hoặc lớn nhất có thể, từ đây ta có thể dùng một biến để quản lý ~prefix~ và ~min~ và ~max~ của đoạn hiện tại.

Độ phức tạp: ~O(n)~.

#include <bits/stdc++.h> // QioCas

#ifdef LOCAL
#include </home/cas/Cp/Lib/debug.h>
#else
#define console(...) void(000)
#endif

using namespace std;
using ll = long long;


int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    int a[n + 1] = {};
    ll ps[n + 1] = {};
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
        ps[i] = ps[i - 1] + a[i];
    }

    ll ans = numeric_limits<ll>::min(), maxz = ps[k], minz = ps[k];
    for(int i = 2 * k; i <= n; ++i) {
        minz = min(minz, ps[i - k] - ps[i - 2 * k]);
        maxz = max(maxz, ps[i - k] - ps[i - 2 * k]);
        ans = max(ans, abs(ps[i] - ps[i - k] - maxz));
        ans = max(ans, abs(ps[i] - ps[i - k] - minz));
    } cout << ans << "\n";
    return 0;
}