Kadane's Quiz
Editorial
12 questions across the two Kadane's lessons: what to carry from value to value, what each update does, and what a small bug does. Pick an answer to see whether it's right and why. Nothing is saved, so you can take it again.
If one trips you up, its lesson is Kadane's Algorithm or Kadane's Algorithm with More State.
Quiz
1 / 12Multiple choice
The largest sum of a contiguous subarray. What do you carry from value to value?
Multiple choice
The largest product of a contiguous subarray. What do you carry?
Multiple choice
The largest sum of a subarray after deleting at most one value from it. What do you carry?
Multiple choice
The longest subarray whose comparisons alternate up and down. What do you carry?
Multiple choice
Kadane's: the best sum ending at the previous value is −3, and the next value is 5. What happens?
Multiple choice
Kadane's with cur = best = 0 at the start. What does it return for [-5, -2, -8]?
Multiple choice
On the walk of running totals, the best subarray ending at a fence is that fence's total minus…
Multiple choice
Circular, with no all-negative check: what does it return for [-4, -1, -3]?
Multiple choice
Kadane's rule with products, cur = max(x, cur * x), on [-3, 4, -2] (the answer is 24). What does it return?
Multiple choice
Products: hi = max(x, hi * x, lo * x), then lo = min(x, hi * x, lo * x). On [-2, 3, -4, -1] (the answer is 24), what does it return?
Multiple choice
One deletion: why does the deletion state start far below any sum, not at 0?
Multiple choice
Longest Turbulent Subarray on [1, 2, 2, 3]. What's the answer?