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?

A

r = 4, window_sum = 7

B

r = 4, window_sum = 4

C

r = 3, window_sum = 5

D

r = 3, window_sum = 2