Maximum Subarray — Animated

Four algorithms for $\max\bigl\{A[i] + \cdots + A[j-1] \;:\; 0 \;\le\; i \;\le\; j \;\le\; n\bigr\}$ on the same input: brute force, reusing sums, divide & conquer, and the linear sweep. Step through them one operation at a time, measure them, or race them against each other. The cost measure throughout is the number of additions.

Algorithm

Input

Show (i,j)

0 / 0

Delay 260ms

Array A[0..n) · state of the algorithm

Status

Press step or play to begin.

Variables

Pseudocode

Cost · additions

Edit / paste an input

Format: whitespace- or comma-separated integers, one array. Comments after # are ignored, so a preset can carry a caption. Example: 31 -41 59 26 -53 58 97 -93 -23 84.

Stepping is meant for small inputs — the brute-force trace has $n(n+1)(n+2)/6$ additions, so $n \;=\; 30$ already means about 5000 of them. Traces are cut off after 40 000 steps; for anything bigger, use the measure and race tabs.

← / → step · Home / End jump to start / end · space plays · click a segment of the phase strip to jump there · drag the grey handles to resize

Algorithm

Bulk … ×

Analysis

log–log

Abstract cost · number of additions

Measured running time · ms per run

Last run

Every point is one execution on one input. Points stay on the plot, so runs accumulate into a curve; colours distinguish the algorithms. Short runs are repeated automatically until they take a few milliseconds, and the reported time is the average of those repetitions — otherwise the clock is too coarse for small n.

Worth noticing: all four algorithms perform a number of additions that depends on n alone, never on the values in the array. So for this cost measure, worst case = best case = average case, and the left plot is a clean function of n. The scatter you see on the right is measurement noise (and cache behaviour), not input-dependence.