mediumDSA

How do you find the maximum subarray sum?

Q: How do you find the maximum subarray sum?

**Intuition.** Scan left to right keeping a **running sum**. The key insight (Kadane's algorithm): if the running sum ever goes negative, it can only *hurt* whatever comes next — so drop it and start fresh from the current element. Track the best sum you ever saw. reset the run when it would go negative; keep the best -2 <rect x="74" y="40" width="50" height="38" rx="5" fill="#22c55e" fill-opacity

818 views

Understand the problem

Explain Kadane's algorithm.

kadanedp

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Stuck? AI Nudge Available

Get a conceptual hint to guide your logic without spoiling the final implementation.

Study the solution

The solution is waiting

Give it an honest attempt first — then compare your thinking with the full walkthrough.

Read the code

Kadane's algorithm

Run Playground

def max_subarray(nums):
    max_ending = best = nums[0]
    for x in nums[1:]:
        max_ending = max(x, max_ending + x)  # extend or restart
        best = max(best, max_ending)
    return best


# --- demo ---
print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))   # 6  -> [4,-1,2,1]

Join the discussion

Discussion (0)

No responses yet. Be the first to share what you think.

How do you sort an array of 0s, 1s, and 2s?

Find the kth largest element in an array