Timeline for Monotonic queues recurrence relation
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 3, 2020 at 23:07 | history | edited | John L. | CC BY-SA 4.0 |
Some people prefer other description of a "DP problem", cs.stackexchange.com/a/79749 or https://medium.com/outco/how-to-solve-sliding-window-problems-28d67601a66
|
| Apr 28, 2020 at 17:07 | comment | added | John L. | Hmm, it is not easy to construct a summary that is suitable for all levels of understanding and the many different variations of the problems. It might be better to read the examples. Then come up with your own mental image and your own summary. Or, similar to "DP problem", this kind of problems can be called "SW problem" for "sliding window problem", where FIFO queues sliding over the given array are used to define and solve the problem. | |
| Apr 28, 2020 at 16:56 | comment | added | John L. |
C could just be a constant. More generally, I would interpret + C to indicate M[i] might not be min(A[j:k]) exactly. Here is another version of the summary, A problem to find M[i] that is (essentially) defined as the minimum of some function on elements of A with indices that are at most i given array A.
|
|
| Apr 28, 2020 at 16:38 | comment | added | DMW | Thank you, that makes a lot of sense. One more quick question in regards to your replacement. Is C a general constant used to denote some arbitrary window length? IE j to K + C length, or is it the minimum value of the range + C. The former seems the case to me? | |
| Apr 28, 2020 at 16:34 | history | edited | John L. | CC BY-SA 4.0 |
Fixed a critical typo.
|
| Apr 28, 2020 at 16:31 | vote | accept | DMW | ||
| Apr 28, 2020 at 16:28 | history | edited | John L. | CC BY-SA 4.0 |
Slightly more explanation.
|
| Apr 28, 2020 at 16:23 | history | answered | John L. | CC BY-SA 4.0 |