Sliding Window
Carrying one value forward
The simplest form of window state: a single number that makes each position answerable on sight.
Key idea
The question to ask
Before reaching for anything elaborate, ask the question from Unit 0: standing at position i, what would I need to know about everything before i in order to answer instantly?
Surprisingly often the answer is a single number. When it is, the whole problem collapses to one pass carrying that number.
Concretely: what is the longest run of strictly increasing values ending at each position? At position i you only need to know how long the run ending at i-1 was.
Why it works
The shape underneath
Two variables with different jobs, and mixing them up is the usual bug. current describes the thing ending exactly here. best is the answer over everything seen so far.
Update current from the previous current and the element you just arrived at. Then fold current into best. Never update best from anything except current, and never let best feed back into current.
Gotcha
Reset to the right value
When the run breaks, current resets to 1, not to 0. The element you are standing on starts a new run of length one all by itself.
Off-by-one resets are the most common bug in this pattern, and they are invisible on inputs where the answer happens not to touch the reset. Test with an input that breaks immediately, such as a strictly decreasing list, where the correct answer is 1.
Tip
Where else one number is enough
The running value does not have to be a length. It can be a minimum seen so far, a maximum, a running total, a count of something, or a running product. What makes the pattern work is that the value can be updated from its own previous value plus one new element, without re-reading anything.
If updating it requires looking back at earlier elements, one number is not enough and you need a real window. That is the next lesson.
You have done this before
The final lab in Unit 0 asked for the largest drop from an earlier value to a later one, carried by remembering the largest value seen so far. The problem below asks a question with the same shape and the opposite direction. Work out which running value it needs before you start.
Predict the output: the reset value
This version resets to 0 instead of 1. Type what it prints for the two calls, separated by a space.
Best Time To Buy And Sell Stock
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.