DSA · Reimagined
JSON All
Arrays medium time O(n) space O(1)

Kadane's Algorithm

Walk left to right keeping the best sum ending here. If that running sum ever goes negative, it can only hurt what follows, so restart from the current element. Track the best window seen.

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

Start: current sum and best are both -2.

cur -2best -2
1 / 14

Practice

Machine twin: /dsa-viz-v2/kadane.json — the full deterministic run as structured data.