Sliding Window

A sliding window maintains information about a contiguous interval as its endpoints move. Fixed-size windows can update sums by adding the entering value and subtracting the leaving one. Variable-size windows need a reason why expanding or shrinking changes feasibility monotonically. We give two separate programs: maximum sum of exactly k values with signed input, and longest interval with sum at most K under nonnegative input.

Prerequisites: Two Pointers; running sums; arrays.

Build the idea

1. 1. Maintain a fixed-length sum

   Sum the first k entries once. To shift one position right, add a[right] and subtract a[right−k]. These are exactly the changes between consecutive k-length intervals, so no inner rescan is needed. Initialize best from the first real window rather than zero, because all candidate sums may be negative.

2. 2. Trace signed fixed windows

   For [2,−1,3,−2,4] and k=3, window sums are 4,0,5. The first shift replaces 2 by −2, changing 4 to 0; the next replaces −1 by 4, changing 0 to 5. Negative values are completely valid for this fixed-size update identity. The contract requires 1≤k≤n so the initial window exists.

3. 3. Add a monotonicity condition for variable length

   For the second task, all entries and limit K are nonnegative. Extend right, then while sum>K remove left values. Removing nonnegative values never increases the sum; extending right never decreases it. Once the window is feasible, its current earliest possible left gives the longest feasible window ending at that right. Each left moves forward at most n times overall.

4. 4. See why negatives break the greedy shrink

   With [5,−4] and limit 1, removing 5 immediately when the first prefix exceeds the limit loses the later valid length-two window whose sum becomes 1. Therefore the second algorithm is not valid for arbitrary signed arrays. That counterexample does not invalidate fixed-size sums, which use no feasibility-based discard rule. For signed variable-length constraints, prefix sums and more advanced structures may be needed.

5. 5. Track empty-window behavior

   The nonnegative program may shrink past right when one value alone exceeds K; its window length becomes zero and sum zero. Zeros are allowed and can extend a valid window without increasing sum. For [1,2,1,1,3], K=4, longest length is 3, such as [1,2,1] or [2,1,1]. Maintaining frequencies instead of sums enables other window invariants, but each needs its own update and validity reasoning.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
int main(){
    int n,k;
    std::cin>>n>>k;
    std::vector<long long>a(n);
    for(auto&x:a){
        std::cin>>x;
    }
    long long current=0;
    for(int i=0;i<k;++i){
        current+=a[i];
    }
    long long best=current; // A real window, even if all sums are negative.
    for(int right=k;right<n;++right){
        current+=a[right]-a[right-k];
        if(current>best){
            best=current;
        }
    }
    std::cout<<best<<'\n';
}

Complexity analysis

Both programs run in O(n) time: fixed windows use one update per shift; variable windows add each element once and remove it at most once. Each stores O(n) input with O(1) auxiliary sum/index state. n≤200000 and |value|≤10^9 keep totals in long long. The second program additionally requires nonnegative values and K.

Example input and output

Fixed program: read n k, 1≤k≤n≤200000, then n signed values |value|≤10^9. Print the largest sum of exactly k consecutive entries.

Input

5 3
2 -1 3 -2 4

Output

5

The three window sums are 4,0,5; the final window [3,−2,4] wins.

Read n K (0≤n≤200000, 0≤K≤10^15), then n NONNEGATIVE values≤10^9. Print longest subarray length with sum≤K; zero is allowed for no nonempty feasible window.

// Key idea: 5. Track empty-window behavior The nonnegative program may shrink past right when one
// value alone exceeds K; its window length becomes zero and sum zero.
#include<iostream>
#include<vector>
int main(){
    int n;
    long long limit;
    std::cin>>n>>limit;
    std::vector<long long>a(n);
    for(auto&x:a){
        std::cin>>x;
    }
    int left=0,best=0;
    long long sum=0;
    for(int right=0;right<n;++right){
        sum+=a[right];
        while(left<=right&&sum>limit){
            sum-=a[left++];
        }
        if(right-left+1>best){
            best=right-left+1;
        }
    }
    std::cout<<best<<'\n';
}

Input

5 4
1 2 1 1 3

Output

3

Three consecutive values can total 4, while every length-four window exceeds 4.

Complexity: O(n) time, O(n) input storage and O(1) auxiliary state.

Practical applications

Use fixed windows for rolling sums/frequencies and variable windows when an explicit monotone validity rule permits irreversible endpoint moves. A monotonic deque can maintain window minima/maxima, taught in Data Structures. Arbitrary signed sum constraints may call for prefix-sum approaches rather than a simple shrink loop.

Check your understanding

Which claim is correct?

Put it into practice

Construct a signed input that defeats the variable-window algorithm.