Maximum Subarray
A medium Arrays problem included in Apna College, Love Babbar 450, Striver A2Z. Below: the roles whose interviews prioritise this topic, and how to practise it.
- Topic
- Arrays
- Sheets
- 3
- Core for
- 25 roles
- Platform
- LeetCode
The problem
Given an integer array, find the contiguous subarray containing at least one element that produces the greatest sum.
Example 1
- Input
- nums = [-2,1,-3,4,-1,2,1,-5,4]
- Output
- 6
- Why
- The contiguous subarray [4,-1,2,1] achieves the maximum sum of 4 + (-1) + 2 + 1 = 6.
Example 2
- Input
- nums = [1]
- Output
- 1
- Why
- The single element forms the only subarray and yields a sum of 1.
Example 3
- Input
- nums = [5,4,-1,7,8]
- Output
- 23
- Why
- The entire array sums to 5 + 4 + (-1) + 7 + 8 = 23, beating every smaller subsegment.
Constraints
- 1 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
How to think about it
Updated 2026-09-09A running prefix sum that drops below zero is an active liability to whatever comes next. Any future subarray would strictly benefit from throwing that negative prefix away and starting fresh from the current number. Walking left to right and making this binary choice at each step boils the problem down to tracking a single running accumulator.
Approaches, worst first
Exhaustive subarray scanning
time O(n^2) · space O(1)
Compute the sum of every possible subarray (i, j) using two nested loops. Directly evaluates every candidate slice in the array, but repeatedly sums overlapping spans and consumes quadratic runtime.
Divide and conquer boundary merge
time O(n log n) · space O(log n)
Split the array in half and recursively find the best subarray in the left half, the right half, and crossing the center. Combines boundary answers efficiently, but adds recursive stack overhead and extra code complexity compared to a linear scan.
Kadane running accumulatorWrite this one
time O(n) · space O(1)
Maintain currentSum and maxSum initialized to nums[0]. For each subsequent element, set currentSum to max(num, currentSum + num) and update maxSum. Discarding negative running sums ensures optimal greedy continuation in a single pass.
Where people lose marks · 3
- Initializing the maximum sum to 0 instead of nums[0] or negative infinity, which causes arrays of entirely negative numbers to incorrectly report 0.
- Resetting currentSum to 0 before updating maxSum on negative numbers, which ignores individual negative values that should be valid answers.
- Assuming the maximum subarray must contain positive numbers, failing on arrays like [-5, -2, -8] where the answer is -2.
Full solution
Kadane's running accumulator: a linear scan that discards any prefix once it turns negative, since no future subarray benefits from carrying it forward. This is the answer an interview expects over the quadratic or divide-and-conquer alternatives.
Python
def max_subarray(nums: list[int]) -> int:
current_sum = max_sum = nums[0]
for num in nums[1:]:
# Drop the running prefix once it becomes a liability; start fresh at num.
current_sum = max(num, current_sum + num)
max_sum = max(max_sum, current_sum)
return max_sum
JavaScript
function maxSubArray(nums) {
let currentSum = nums[0];
let maxSum = nums[0];
for (let i = 1; i < nums.length; i++) {
// Drop the running prefix once it becomes a liability; start fresh at num.
currentSum = Math.max(nums[i], currentSum + nums[i]);
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}
The theory behind it
Arrays — the ground this problem stands on. All Arrays problems
What Arrays is
An array is a row of fixed boxes laid side by side in computer memory, like numbered lockers in a hallway. Because each box occupies identical space and sits directly next to its neighbors, jumping to locker zero or locker ten thousand takes the exact same tiny fraction of time. Every box holds an item of the same type, addressed by an offset number called an index.
When to reach for it
Reach for an array when items arrive in a known sequence and need immediate retrieval by position number. Problems asking for running totals, prefix accumulations, cyclic rotations, or in-place rearrangements signal array mechanics. Whenever constraints require constant-time random lookups or contiguous cache scans across fixed collections, a flat sequence is the default container.
How the pattern works
Visualize a tape with zero-indexed slots stretching from start to end. Keep track of write and read cursors when modifying contents without allocating helper buffers. For running computations, maintain an invariant such as having processed all elements left of the current index while pending elements wait to the right. When modifying entries in place, consider scanning backwards from the end so unread data is not overwritten.
What each operation costs
| Operation | Time |
|---|---|
| look up element by index | O(1) |
| insert or delete at the start | O(n) |
| search an unsorted collection for a value | O(n) |
What usually goes wrong with Arrays
- Reading past the final index by checking index less than or equal to length instead of strictly less than length, triggering index out of bounds exceptions.
- Modifying length or removing elements during a forward iteration loop, which causes remaining items to shift left and skip validation on the next neighbor.
- Assuming dynamic resizing is costless inside nested loops, causing repeated memory reallocation copies when appending unknown quantities of items.
Which roles need this problem
Arrays is a core topic for these 25 roles — if you're targeting one of them, this problem is early in your path, not optional.
Secondary for 3 more roles, including Database Engineer, Bioinformatics Engineer, Networking Engineer.
Track this in your role's order
Pick your target role and all 370 problems — including this one — resequence to what that interview actually asks. Free.
Start freeMore Arrays problems
Problem set and role mapping as of .