visual walkthrough
Maximum Average Subarray I
The textbook fixed window: add the new element, drop the old one.
The idea
Windows of the same size overlap almost completely: moving one step right drops one number and adds one. So the new sum is the old sum, plus the number that enters, minus the number that leaves.
The maximum average is just the maximum sum divided by k.
Complexity
| approach | time | space |
|---|---|---|
| Re-add every window | O(n · k) | O(1) |
| Slide the sum | O(n) | O(1) |