まず、累積和を予め求めます。

\(B_i=A_1+A_2+\dots+A_i\) とします ( \(B_0=0\) とします)。

答えは \(B_K-B_0,B_{K+1}-B_1,\dots,B_{N}-B_{N-K}\) の中の最大値から最小値を引いたものとなります。

全ての計算は時間計算量 \(O(N)\) で完了します。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int N,K;
  cin >> N >> K;
  vector<int> A(N+1,0);
  for(int i=1;i<=N;i++){
    cin >> A[i];
    A[i]+=A[i-1];
  }
  int low=1e9,high=-1e9;
  for(int i=K;i<=N;i++){
    int cur=A[i]-A[i-K];
    low=min(low,cur);
    high=max(high,cur);
  }
  cout << high-low << "\n";
  return 0;
}