Given an integer array `nums`, find the contiguous subarray with the largest sum and return that sum.
Example: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] → 6 (from [4, -1, 2, 1])
Brute force: Sum every contiguous subarray and keep the maximum. (time O(n²), space O(1))
No visualization loaded.
Watch
—
i
Press Run to begin.
0/0
Why the best approach wins
Brute force recomputes overlapping sums for every (i, j) pair — O(n²). Kadane's insight: a running prefix that has gone negative can only hurt what follows, so you drop it and start fresh. That collapses the work into a single O(n) pass with O(1) memory.
Brute force: O(n²) time / O(1) spaceKadane's algorithm: O(n) time / O(1) space
Your turn — implement maxSubArray
Loading editor…