Books In Five Minutes
The USACO Guide sliding window for the longest prefix-free segment with sum at most T:
r, window_sum, ans = -1, 0, 0
for l in range(N):
while r + 1 < N and window_sum + A[r + 1] <= T:
r += 1
window_sum += A[r]
ans = max(ans, r - l + 1)
window_sum -= A[l]
Run it with A = [2, 3, 1, 1, 2], N = 5, T = 5.
| l | r after the inner loop | window_sum after the inner loop | ans |
|---|---|---|---|
| 0 | 1 | 5 | 2 |
| 1 | 3 | 5 | 3 |
| 2 | ? | ? | 3 |
What are r and window_sum when the inner loop finishes for l = 2?
Sign in to answer questions and track your progress
Sign In