Sliding Window
22 / 170Sliding WindowLesson 1 of 6About 28 min
The simplest form of window state: a single number that makes each position answerable on sight.
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.
def longest_increasing_run(values): if not values: return 0 best = current = 1 for i in range(1, len(values)): if values[i] > values[i - 1]: current += 1 else: current = 1 # the run is broken, start over here best = max(best, current) return best print(longest_increasing_run([1, 2, 1, 2, 3, 4, 1]))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.
This version resets to 0 instead of 1. Type what it prints for the two calls, separated by a space.
def buggy_run(values): best = current = 0 for i in range(1, len(values)): if values[i] > values[i - 1]: current += 1 else: current = 0 best = max(best, current) return best print(buggy_run([1, 2, 3]), buggy_run([3, 2, 1]))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.