Back to course

Windows, Prefixes and Monotonic Stacks

A large share of the array problems in these assessments are one of three patterns. Learning to tell them apart is worth more than learning any of them individually, because the recognition takes ten seconds and the implementation takes five minutes.

Kadane, and what it is really doing

Maximum-sum contiguous subarray is a recurring warm-up question and the canonical example. The solution is four lines, and the reason it works is one sentence: the best subarray ending at position ii either extends the best one ending at i−1i-1 or starts fresh at ii.

bi=max⁡(ai,  bi−1+ai),answer=max⁡ibib_i = \max(a_i,\; b_{i-1} + a_i), \qquad \text{answer} = \max_i b_i

The rest of this lesson is for subscribers

Unlock every lesson in Programming for Quantitative Developers, and every other premium course.

Subscribe to continue

Test your knowledge

Questions are only available to subscribers.
Continue
NextIntervals and Sweep Lines

Keep reading Programming for Quantitative Developers

25 lessons in this course, and every other premium course, on one subscription.

Subscribe now
  • Every lesson in every course, with the worked examples and interactive simulators
  • Graded questions on every lesson, with explanations for the wrong answers as well as the right one
  • The trainers, timed assessments and brainteaser library that go with them