How to use the Kadane's Algorithm Visualizer
- 1. Set it upType numbers separated by commas; negatives are allowed.
- 2. RunPress Visualise.
- 3. ReplayStep through: the current subarray is blue, the best so far is green.
Worked example
For −2, 1, −3, 4, −1, 2, 1, −5, 4, the answer is 6, from the subarray 4, −1, 2, 1 at indexes 3–6. At index 3 the value 4 beats extending the running sum (−2 + 4 = 2), so the subarray restarts there. Adding −1, 2 and 1 gives 6, the best. Adding −5 drops the running sum to 1, and the final 4 brings it to 5, still below 6. Checking every subarray would mean 45 sums for these 9 numbers; Kadane needs one pass.
The one rule
At each number the algorithm asks: is it better to extend the subarray ending at the previous number, or to start a new one here? In code, cur = max(x, cur + x) and best = max(best, cur). A negative running sum can only hurt what comes next, which is why the algorithm drops it. Starting both values at the first element, not at 0, makes all-negative arrays work: for −3, −1, −2 the answer is −1.
Where it shows up
Maximum Subarray is in the Blind 75 list and many fresher tests. The same idea of keeping the best answer that ends here appears in stock profit problems, the maximum product subarray (track the minimum too), and circular arrays (total minus the minimum subarray).
Frequently asked questions
Does it work with all negative numbers?
Yes. It returns the largest single number.
Is this dynamic programming?
Yes. cur is the best sum of a subarray ending at the current index, built from the previous one.
How many numbers can I enter?
Up to 30, so the replay stays readable.
Is the Kadane visualizer free?
Yes. You can use the Kadane visualizer without signing up. The first time you run it, we ask once for your name and WhatsApp number; after that the Kadane visualizer and every other Uncodemy tool open straight away.