The queue method is popular, but there's a much faster (branch-free) and in my opinion simpler way, known as the van Herk/Gil-Werman algorithm in image processing. It splits the input into windows and pairs up a backward scan on one window with a forward scan on the next. This works for any associative function. I was very surprised when I learned about it that it's not taught more often (the name's not doing it any favors)! And I wrote a tutorial page on it for my SIMD-oriented language, mostly about vectorizing it which I didn't quite finish writing up, but with what I think is a reasonable presentation in the first part: https://github.com/mlochbaum/Singeli/blob/master/doc/minfilt...
EDIT: On closer inspection, this method is equivalent to the one I described, and not the one I'm used to seeing with queues (that starts my tutorial). The stack-reversing step is what forms a backwards scan. The combination of turning it sequential by taking in one element at a time but then expressing this in functional programming makes for a complicated presentation, I think.
This is similar to an approach I use but instead of a queue, I accomplish this using a ring buffer that wraps around and overwrites entries older than window size. We maintain a global window aggregate, subtract ring buffer slot aggregate for entries dropping out and accumulate new entries into new slot aggregate while adding it to the global aggregate. Everything is o(1) including reads, which just returns the global window aggregate.
Yes, but how do you update your max when you drop old values. That's the issue with max forming a monoid and not a group.
The whole point of the post is that this is easy to implement for sum, but is difficult for max. Posting how someone solves the problem for sum isn't really addressing anything new here.
That was a well written and easily approachable blog post on what I found to be an interesting topic. Aside from the topic itself, I think I also learned a bit about structuring technical articles.
Competitive programming demands tight control over execution time and memory attributes best served by languages that offer strict evaluation and low-level data manipulation. Haskell has lazy evaluation, what can lead to unpredictable performance and space leaks. Monads are abstraction layers...
Well, it depends on how you measure competitive programming. I think for measuring it in O() terms - as every paper out there on data structure does -, Haskell is quite good for the task.
I also found an interesting streaming version here recently: https://signalsmith-audio.co.uk/writing/2022/constant-time-p...
EDIT: On closer inspection, this method is equivalent to the one I described, and not the one I'm used to seeing with queues (that starts my tutorial). The stack-reversing step is what forms a backwards scan. The combination of turning it sequential by taking in one element at a time but then expressing this in functional programming makes for a complicated presentation, I think.