Maximum Subarray: Kadane's Algorithm in Python and TypeScript

The Maximum Subarray Problem

You are given an array of integers, which can include negative numbers. Find the contiguous subarray (at least one element long) with the largest sum, and return that sum.

Example 1

Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6
Why: the run [4, -1, 2, 1] adds up to 6. Including the -1 is worth it, because the 2 and 1 after it more than make up for it.

Example 2

Input: [-3, -1, -2]
Output: -1
Why: every number is negative, so the best you can do is the single largest number. Returning 0 here is the most common bug.

Assumptions to confirm

• Must the subarray be non-empty? (Usually yes, which is why the all-negative case returns the largest number, not 0.)
• Do you need the sum only, or also where the run starts and ends?
• Can the array be empty? (Usually not; ask what to return if it can.)

Start With the Brute Force

Try every start index, and for each one extend the end index while keeping a running total. Record the largest total you see. That checks every subarray in O(n²) time with O(1) extra space. (Recomputing each sum from scratch would be O(n³), so mention the running total.)

Then look for the repeated work. For each new end position you consider many start positions, but you only ever need the best sum of a run that ends right there. If you know the best run ending at the previous position, the best run ending at this position is easy to work out. That observation is Kadane's algorithm.

The Optimal Approach: Kadane's Algorithm

Maximum Subarray Solution in Python and TypeScript

Both versions start from the first element rather than 0, which is what makes them correct when every number is negative.

Python

def max_subarray(nums: list[int]) -> int:
    best = current = nums[0]
    for num in nums[1:]:
        # Either extend the run ending here, or start a new run at num.
        current = max(num, current + num)
        best = max(best, current)
    return best

TypeScript

function maxSubArray(nums: number[]): number {
  let best = nums[0];
  let current = nums[0];
  for (let i = 1; i < nums.length; i++) {
    // Either extend the run ending here, or start a new run at nums[i].
    current = Math.max(nums[i], current + nums[i]);
    best = Math.max(best, current);
  }
  return best;
}

To return the subarray itself, also record the index where the current run started (reset it whenever you restart) and copy the start and end into the best range whenever the best sum improves.

Time and Space Complexity

How to Talk Through Maximum Subarray in an Interview

A strong spoken answer follows the same five beats every time:

1. Clarify: "Must the subarray be non-empty? What should I return if every number is negative?"
2. Brute force: "I can try every start and extend the end with a running total, which is O(n²)."
3. Optimise: "I only need the best run ending at each position. That is either this number alone or the previous best run plus this number, so one pass is enough."
4. Code: say why you start from the first element and not from 0.
5. Test: walk through the nine-number example, then [-3, -1, -2], then a single element. State O(n) time and O(1) space.

If you can explain Kadane's algorithm as "extend or restart", you have also explained the core idea of dynamic programming, which interviewers often probe next.

Edge Cases and Common Follow-Ups

Practise Maximum Subarray in a Mock Coding Round

Maximum Subarray rewards a clear one-line explanation more than clever code. Interviewers want to hear why restarting the run is safe, and the all-negative case is where many candidates stumble when they are nervous. Practising it out loud makes that explanation automatic.

MockIF runs mock coding interviews with a voice AI interviewer in a real in-browser editor, in Python and TypeScript. It runs your code against tests, asks you to explain your approach, adds follow-up questions the way a real interviewer would, and then scores your answer and gives specific feedback. Each session costs 2 credits. It is free to start with 5 credits, then monthly or 3-monthly plans, or one-off credit packs (see pricing).

Frequently Asked Questions