Maximum Subarray
Find the contiguous subarray with the largest sum and return that sum.
Open on LeetCode ↗Intuition
At each position, ask one local question: does the running sum still help me, or is the current element better on its own? If the running sum has gone negative, it can only drag the future down, so drop it and restart. That is Kadane's algorithm.
Approach
Brute force enumerates too much
There are O(n²) subarrays, and summing each is another factor of n if done naively — O(n³), or O(n²) with running sums. That's a lot of work, and most of it overlaps: the sum of a long subarray shares almost everything with the subarray one element shorter. The trick is to stop thinking about all subarrays at once and instead ask a single local question as we move.
Ask: what's the best subarray ending right here?
Define cur = the largest sum of any subarray that ends exactly at the current index. There are only two choices for that: either we extend the best subarray ending at the previous index (cur + num), or we abandon it and start a brand-new subarray at the current element (num). We take whichever is larger: cur = max(num, cur + num). The deep reason a restart is ever better is simple — if cur has gone negative, it can only drag down whatever comes next, so carrying it is strictly worse than starting fresh. This is Kadane's algorithm.
Track the global best alongside the local one
cur is the best ending here; the answer is the best ending anywhere, so keep a separate best and update best = max(best, cur) each step. Seed both with nums[0] (not 0) so that an all-negative array correctly returns its least-negative element rather than a phantom empty subarray of 0. One pass, O(n) time, O(1) space.
Solution & live demo
Edge cases
Seeding best with nums[0] (not 0) means the least-negative single element is returned, which is correct.
Loop body never runs; best equals that element.
cur keeps the running sum as long as it stays positive, so a small negative valley is bridged rather than discarded.