整数 \(L\) を全探索することを考えます。カゴの左端が \(1\) より外に出たり、カゴの右端が \(N\) より外に出たりすると無駄になることに注意すると、\(L\) として考慮するべきは \(1\) 以上 \(N-W+1\) 以下の値です。よって次のような二重ループのコードが書けます。

ans = 0
for L in 1 to (N-W+1):
  sum = 0
  for i in L to (L+W-1):
    sum += A[i]
  ans = max(ans, sum)
print(ans)

このアルゴリズムの計算量は \(O(N^2)\) であり、このまま実装すると TLE になります。内側のループで行っている \(A_L+\ldots+A_{L+W-1}\) の計算の高速化を考えます。

\(S_0=0\)、\(S_i=S_{i-1}+A_i\) となる配列 \(S\) を用意します。この \(S\) により、\(A_L+\ldots+A_{L+W-1}=S_{L+W-1}-S_{L-1}\) と \(O(1)\) で計算することができるようになり、計算量は全体で \(O(N)\) になります。

実装の際は添字に注意してください。

実装例(Python)

N, W = map(int,input().split())
A = list(map(int,input().split()))

S = [0]
for a in A:
  S.append(S[-1]+a)

ans = 0
for L in range(N-W+1):
  ans = max(ans, S[L+W]-S[L])
print(ans)