How do you find the maximum subarray sum?

Q: How do you find the maximum subarray sum?

**Target Audience:** Beginners preparing for coding interviews; you should know arrays and loops. **Difficulty:** Medium **Language:** Python 3 > **How to read this doc:** every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged `📌 Interview term:` with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the **Verified** section is copied from that run. ## 1. Why This Even Matters — A Story First A lemonade stand keeps a notebook of each day's profit or loss: `-2, 1, -3, 4, -1, 2, 1, -5, 4`. At the end of the summer the owner asks: "Which run of **consecutive** days made the most money?" She cannot pick and choose single good days — she wants a stretch, from some start day to some end day, because she is deciding when to open next year. Checking every possible stretch works, but a summer has 90 days and th

The problem

Question presented to candidate: "Given an integer array, find the contiguous subarray with the largest sum and return that sum. Code it in Python. What if every number is negative? Can you also return where the subarray starts and ends?"

What a strong answer should cover:

The state "best sum of a subarray ending here" and the update cur = max(x, cur + x), best = max(best, cur) — Kadane, O(n) time, O(1) space.
Why a negative running sum should be dropped, and that the two forms (restart if cur < 0 / max(x, cur + x)) are the same rule.
Initialising from the first element so all-negative arrays return their largest element, not 0.
The brute-force baselines (O(n³), O(n²)) and the prefix-sum view; tracking start and end indices.
Python specifics: starting from nums[0] rather than 0 or float("-inf"), IndexError on an empty list, slicing being end-exclusive for returning the subarray, and int never overflowing.

Clarifying questions expected:

"Must the subarray be non-empty, and what should an empty input return?"
"Do you want the sum only, or the indices too?"

Code / implementation expected: Yes — a one-pass Python function, with indices as a follow-up.

kadane
dp

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews; you should know arrays and loops. Difficulty: Medium Language: Python 3

How to read this doc: every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged 📌 Interview term: with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the Verified section is copied from that run.

1. Why This Even Matters — A Story First

A lemonade stand keeps a notebook of each day's profit or loss: -2, 1, -3, 4, -1, 2, 1, -5, 4. At the end of the summer the owner asks: "Which run of consecutive days made the most money?" She cannot pick and choose single good days — she wants a stretch, from some start day to some end day, because she is deci

The solution is hidden so you can try first

11 min read · 12 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonKadane with the winning subarray and its indices, against the start-at-zero bug

Practice

PythonFour methods side by side: O(n^3), O(n^2), prefix sums and Kadane, with addition counts