CodeWithYash

Intermediate · Module 8 · Lesson 4

Kadane’s algorithm

Choose whether to extend or restart a subarray.

15–25 min readLesson 45 of 123 Interactive Lab
Jump to interactive visualizer

Lesson 45 of 123

1d streak

Interactive Visualization

Trace the algorithm state by state

Change the inputs, run an operation, and connect each visible state change to the explanation below.

Dynamic programming pattern

Kadane’s Algorithm

Index

0

Choice

initialize

Current

-2

Best

-2

start
-2
0
1
1
-3
2
4
3
-1
4
2
5
1
6
-5
7
4
8

Invariant

current is the best subarray ending exactly at this index; best is the best subarray seen anywhere so far.

Step 1 / 9

Theory lesson · Step-by-step

Understand Kadane’s algorithm

Choose whether to extend or restart a subarray.

Worked approach

Trace the reasoning step by step

  1. 1Define the cumulative or best-ending state required by Kadane’s algorithm.
  2. 2Initialize the identity or first-element base case explicitly.
  3. 3Update the current state from the previous state and current value.
  4. 4Combine directional states or subtract boundaries using matching index conventions.
  5. 5Test all-negative values, empty prefixes, single cells, and boundary queries.

Concrete example

Find the maximum subarray in [-2,1,-3,4,-1,2,1,-5,4].

  1. 1Restart at 4 when the prior ending sum hurts.
  2. 2Extend through -1,2,1 to reach 6.

Best range [4,-1,2,1] has sum 6.

What must remain true (Loop Invariant)

Each stored prefix, suffix, or ending-state value in Kadane’s algorithm summarizes exactly its declared contiguous range.

Cost Model

Complexity & Trade-offs

Best subarray scan
O(n)
O(1)
The bound follows from the number of states visited and the work performed per transition.

When to use it

  • Range queries, range updates, directional products, and best contiguous scores.
  • Replacing repeated range scans with cumulative state.
  • Combining left and right summaries.

Common mistakes

  • Mixing inclusive and exclusive prefix conventions.
  • Using zero as Kadane’s base when a non-empty all-negative answer is required.
  • Subtracting the wrong boundary or forgetting a neutral prefix.

Practice prompts

  • Reproduce the worked Kadane’s algorithm example without looking at the trace.
  • Change one input condition and explain whether the Kadane’s algorithm invariant still holds.
  • Implement the approach, derive its cost, and compare it with a straightforward baseline.

Mastery check

Can you derive it instead of memorizing it?

State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.