Algorithm dossier

  • Category: DP
  • Worst-case complexity: O(n)
  • Approach: DP
  • Data structure: Array
  • First formalised: 1980s

Why this snippet is Kadane's Algorithm

Why Kadane. One pass, two accumulators. s is the best sum *ending at* the current index — either extend the previous run (s + a[i]) or restart from a[i] alone. b tracks the all-time best. The whole thing collapses what looks like a quadratic problem (try every (i, j) range) into O(n) by exploiting the recurrence s[i] = max(a[i], s[i-1] + a[i]). Classic interview. Asked at every level — the canonical "DP in disguise" question.

How to read a redacted algorithm

Algodle strips identifier names so the snippet has to be read for its shape: the control flow, the data structures it manipulates, the order in which it visits its input. Loops with two pointers crawling toward each other are usually search or partition. A recursion that splits its input in half and recurses on both halves is divide-and-conquer. A priority queue plus graph traversal is almost certainly Dijkstra, Prim, or A*. Six hint columns — category, complexity, approach, data structure, era — let you triangulate even when the snippet itself is opaque.