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.
Reach for Kadane whenever the question asks for the best contiguous run and you catch yourself planning nested loops over start and end. The unlock is asking a local question instead of a global one: "what is the best subarray ending exactly here?" That has a one-line answer — extend or restart — and the global best is just the maximum of those. Maximum product subarray and best-time-to-buy-and-sell-stock are the same shape.
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
Common pitfalls
Initialising cur and best to zero
cur = best = 0
for n in nums:
cur = max(n, cur + n)
best = max(best, cur)cur = best = nums[0]
for n in nums[1:]:
...On an all-negative array like [-3, -1, -2] the answer is -1, but a zero seed reports 0 — an empty subarray, which the problem forbids. Starting from nums[0] guarantees at least one element is always chosen.
Updating best before cur
best = max(best, cur) cur = max(n, cur + n)
cur = max(n, cur + n) best = max(best, cur)
best would then record the window ending at the previous element and never see the final one, so the last position can never win. Compute the new local best first, then let it compete globally.
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.