Introduction

A lot of interview questions sound complicated until you identify the one-pass invariant hiding inside them. A classic example is the maximum subarray problem, which asks for the largest possible sum of a contiguous slice of an array and has a clean linear-time solution known as Kadane's algorithm.

The Problem Statement

Given an array of integers, possibly containing negative values, return the maximum sum of any contiguous subarray. For the array [4, -1, 2, 1, -5, 4], the answer is 6 because the best slice is [4, -1, 2, 1].

A brute-force approach checks every possible start and end index. That works, but it takes quadratic time or worse. Interviewers usually expect you to notice that you only need information about the best subarray ending at the current position.

The Linear-Time Insight

At each index there are only two sensible choices:

• extend the previous subarray
• start a new subarray at the current value

If the running sum before the current element is negative, carrying it forward only hurts the result. So the local state is:

• 'best_ending_here: the best sum of a subarray that must end at the current index'
• 'best_so_far: the best sum seen anywhere in the scan'

That yields the recurrence:

• 'best_ending_here = max(value, best_ending_here + value)'
• 'best_so_far = max(best_so_far, best_ending_here)'

The array is scanned once, so the time cost is linear and the extra memory is constant.

Python Implementation

1def max_subarray_sum(nums):
2    if not nums:
3        raise ValueError("nums must not be empty")
4
5    best_ending_here = nums[0]
6    best_so_far = nums[0]
7
8    for value in nums[1:]:
9        best_ending_here = max(value, best_ending_here + value)
10        best_so_far = max(best_so_far, best_ending_here)
11
12    return best_so_far
13
14
15print(max_subarray_sum([4, -1, 2, 1, -5, 4]))
16print(max_subarray_sum([-8, -3, -5]))

This prints 6 and -3. The second case matters because the correct answer for an all-negative array is the largest single value, not 0.

Track The Actual Subarray

Interview follow-up questions often ask for the indices or the slice itself. You can keep the running start position and update the final answer whenever a better segment appears.

1def max_subarray(nums):
2    if not nums:
3        raise ValueError("nums must not be empty")
4
5    best_sum = nums[0]
6    current_sum = nums[0]
7    best_start = best_end = 0
8    current_start = 0
9
10    for i in range(1, len(nums)):
11        if nums[i] > current_sum + nums[i]:
12            current_sum = nums[i]
13            current_start = i
14        else:
15            current_sum += nums[i]
16
17        if current_sum > best_sum:
18            best_sum = current_sum
19            best_start = current_start
20            best_end = i
21
22    return best_sum, nums[best_start:best_end + 1]
23
24
25print(max_subarray([4, -1, 2, 1, -5, 4]))

That prints (6, [4, -1, 2, 1]).

Why This Works

Kadane's algorithm works because any optimal subarray ending at position i depends only on the optimal subarray ending at position i - 1. If that previous sum is negative, dropping it always improves the result. This is a dynamic programming idea, but with only one state carried forward.

It is a good interview problem because the brute-force version is obvious, the optimized version is elegant, and the proof is small enough to explain out loud.

Variants You Might Be Asked

Common variations include:

• circular arrays, where the best subarray may wrap from the end back to the beginning
• fixed-length windows, which are solved differently
• maximum product subarray, where negative values make the state more complex
• two non-overlapping subarrays, which needs extra precomputation

When you hear one of these variants, do not force Kadane's algorithm blindly. First ask what property changed and whether the one-pass recurrence still holds.

Common Pitfalls

A frequent mistake is initializing the running sum to 0. That breaks all-negative inputs because it returns 0 instead of the best negative number. Initialize from the first array element instead.

Another mistake is confusing contiguous with arbitrary subset. This problem is about adjacent elements. Once you are allowed to skip positions, the problem changes completely.

The last issue is offering the recurrence without explaining why it is valid. In interviews, the explanation matters as much as the code. State clearly that a negative prefix can never help a future sum.

Summary

• The maximum subarray problem has a linear-time solution using Kadane's algorithm.
• Track the best subarray ending at the current index and the best answer overall.
• Initialize from the first element so all-negative arrays are handled correctly.
• Extend the approach with indices when the interviewer wants the actual slice.
• Always explain the invariant, not just the final code.