4 ms·
This is a very interesting algorithm which is more or less known in the folklore, but is still relatively obscure. I have used it as a part of temporal logic mo
by agnishom 2y ago
This is a very interesting algorithm which is more or less known in the folklore, but is still relatively obscure. I have used it as a part of temporal logic monitoring procedure: https://github.com/Agnishom/lattice-mtl/blob/master/src/Monitor/AggQueue.v https://github.com/Agnishom/lattice-mtl/blob/master/src/Moni...
- Groxx 2y agoNot sure I'd call it obscure: https://leetcode.com/problems/maximum-subarray/ https://leetcode.com/problems/maximum-subarray/ I've seen it in tech interviews for years.
- JohnKemeny 2y agoThe blog post discusses something else than just sum. Given an n length array of integers, and an integer k, output the max value for each k sized contiguous subarray. sum is much easier than max.
- yorwba 2y agoThe Leetcode question for sliding window maximum is https://leetcode.com/problems/sliding-window-maximum/ https://leetcode.com/problems/sliding-window-maximum/ Which can be solved using a specialized implementation for max. But the article even discusses a generic solution for any monoid. Either sum or max is easier than sum and max and a bunch of other operations all at the same time.