Introduction

The maximum subarray problem asks for the contiguous subarray with the largest possible sum. It is a classic interview and algorithm problem because the brute-force approach is easy to understand, but the optimal solution is much faster once you see the recurrence. The standard answer is Kadane's algorithm, which solves the problem in linear time. It is one of the clearest examples of dynamic programming reducing an apparently combinatorial search to a simple running decision.

The Core Idea Behind Kadane's Algorithm

As you scan the array from left to right, keep track of two quantities:

• the best subarray sum ending at the current index
• the best subarray sum seen anywhere so far

At each element, you decide whether it is better to:

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

That decision gives the recurrence:

best_ending_here = max(value, best_ending_here + value)

Python Implementation

1def max_subarray(nums):
2    best_ending_here = nums[0]
3    best_so_far = nums[0]
4
5    for value in nums[1:]:
6        best_ending_here = max(value, best_ending_here + value)
7        best_so_far = max(best_so_far, best_ending_here)
8
9    return best_so_far
10
11
12print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))

For the example above, the answer is 6, produced by the subarray [4, -1, 2, 1].

The time complexity is O(n) because the array is scanned once. The extra space complexity is O(1) because only a few variables are stored.

Tracking the Actual Subarray

Sometimes you need the indices, not just the sum. You can extend Kadane's algorithm slightly to record where the best range starts and ends.

1def max_subarray_with_indices(nums):
2    best_ending_here = nums[0]
3    best_so_far = nums[0]
4    start = end = temp_start = 0
5
6    for i in range(1, len(nums)):
7        if nums[i] > best_ending_here + nums[i]:
8            best_ending_here = nums[i]
9            temp_start = i
10        else:
11            best_ending_here += nums[i]
12
13        if best_ending_here > best_so_far:
14            best_so_far = best_ending_here
15            start = temp_start
16            end = i
17
18    return best_so_far, start, end
19
20
21print(max_subarray_with_indices([-2, 1, -3, 4, -1, 2, 1, -5, 4]))

This version returns both the maximum sum and the subarray boundaries.

Why the Brute-Force Approach Is Worse

A brute-force solution checks every possible subarray and computes its sum. Even with some optimization, it is still much slower than Kadane's algorithm for large inputs.

The conceptual advantage of brute force is clarity. The practical advantage of Kadane's algorithm is that it proves you never need to keep a subarray prefix that already hurts the current sum.

The All-Negative Case

A common bug is initializing the running sum to 0 and resetting whenever it becomes negative. That works only if the problem allows the empty subarray. The usual maximum-subarray definition requires at least one element, so an all-negative input must return the least negative element.

That is why the implementation starts from nums[0] instead of 0.

Common Pitfalls

• Initializing the best sum to 0 and failing on all-negative arrays.
• Forgetting that the subarray must be contiguous.
• Solving the problem with nested loops when a linear scan is available.
• Returning the sum only when the caller also needs the start and end indices.
• Confusing maximum subarray with maximum subsequence, which is a different problem.

Summary

• The maximum subarray problem asks for the highest-sum contiguous range.
• Kadane's algorithm solves it in O(n) time and O(1) extra space.
• The key step is deciding whether to extend the current subarray or start fresh at the current element.
• Correct initialization is important for all-negative arrays.
• A small extension of Kadane's algorithm can also return the subarray boundaries.