Maximum Subarray

Resetting a running sum to zero looks like the obvious solution—until the array contains only negative numbers. Then the algorithm can quietly return an empty subarray even though the contract requires a nonempty one.

The reliable Maximum Subarray solution is a one-dimensional dynamic program:

• current stores the best sum of a nonempty subarray ending at the current element.
• answer stores the best sum found anywhere so far.
• Each element either starts a new subarray or extends the best subarray ending immediately before it.

That gives O(n) time and O(1) auxiliary space.

Read the contract and spot the pattern

The input is a nonempty integer array:

• 1 <= len(nums) <= 10^5
• Values may be positive, negative, or zero.
• The selected subarray must be contiguous.
• The selected subarray must be nonempty.
• The function returns only its maximum sum, not its boundaries.

A subarray is different from a subset or subsequence. In [4, -1, 2], [4, 2] is not a valid subarray because it skips an element. You are choosing an uninterrupted segment, not an arbitrary collection.

That contiguity constraint gives us a useful recognition cue:

When a valid solution must end at the current position, ask whether its best value can be derived from the best solution ending at the previous position.

For Maximum Subarray, the answer is yes. Scan from left to right. At each index, maintain the best sum of a nonempty contiguous segment that ends exactly there. Separately, preserve the best ending-state value seen anywhere.

The optimization is not a mysterious trick. It is a compressed DP state.

Use brute force to expose the repeated work

The direct approach enumerates every possible start and end index. For each start, extend the range one element at a time and maintain its sum:

def max_subarray_brute_force(nums):
    best = nums[0]

    for start in range(len(nums)):
        current = 0

        for end in range(start, len(nums)):
            current += nums[end]
            best = max(best, current)

    return best

There are O(n^2) possible contiguous ranges, so this takes O(n²) time and O(1) auxiliary space.

You can use prefix sums to calculate any chosen range sum in constant time, but that does not solve the main problem. You would still need to inspect too many start/end pairs. Prefix sums make each candidate cheaper; they do not reduce the number of candidates.

With an input length of up to 10^5, the better question is:

What summary of the previous position is sufficient to evaluate the current position?

The answer is the best sum of a valid subarray ending at the previous index.

Define the best-ending-here state

Let:

dp[i] = the largest sum of any nonempty contiguous subarray whose final element is nums[i]

The phrase ending at i does important work. It means the candidate must include nums[i], and it cannot jump over elements. That preserves the subarray requirement while reducing the relevant history to one previous state.

Do not confuse dp[i] with the best sum anywhere in the prefix nums[0:i+1].

For example, suppose:

nums = [4, -10, 3]

The best subarray ending at index 1 is [4, -10], with sum -6. But the best subarray anywhere in the prefix through index 1 is [4], with sum 4.

These are different obligations:

• dp[i]: best valid sum that must end at i
• answer: best valid sum anywhere among the elements processed so far

The final result is the maximum of all ending states.

Derive restart versus extend

Consider a subarray whose final element is nums[i]. There are exactly two ways it can be formed:

1. Start a new subarray at nums[i].
2. Append nums[i] to a subarray ending at i - 1.

For the second option, we only need the best subarray ending at i - 1. If another subarray ending there had a smaller sum, appending the same nums[i] would keep it smaller.

Therefore:

dp[i] = max(nums[i], dp[i - 1] + nums[i])

The rolling form is:

current = max(x, current + x)

This is the restart-or-extend decision:

• x: discard the previous segment and start here
• current + x: keep the previous segment and extend it

A negative carried sum is dead weight. Extending it makes the new sum smaller than starting fresh at the current element. A positive carried sum may be worth keeping because it increases the next total.

That intuition is useful, but the state definition is safer than intuition alone. It handles zeros and all-negative input without special-case guessing.

Trace the state

Use the standard mixed example:

[-2, 1, -3, 4, -1, 2, 1, -5, 4]

Track the best sum ending at each position and the best sum seen anywhere:

Index	Value	Best ending here	Best anywhere
0	-2	-2	-2
1	1	1	1
2	-3	-2	1
3	4	4	4
4	-1	3	4
5	2	5	5
6	1	6	6
7	-5	1	6
8	4	5	6

At index 1, extending -2 would produce -1, so the state restarts at 1.

At index 4, the value is -1, but extending the previous sum gives 4 + (-1) = 3, which is better than starting at -1. The negative element stays inside the eventual optimal subarray because the surrounding positive values more than compensate for it.

At index 7, the running ending-state falls from 6 to 1. That does not erase the global answer. The best subarray seen so far is still [4, -1, 2, 1], with sum 6.

The local state moves. The global answer remembers.

Prove the recurrence, then compress the DP

The recurrence follows by induction over the ending index.

For the base case, the only nonempty subarray ending at index 0 is [nums[0]], so:

dp[0] = nums[0]

For any later index i, every nonempty contiguous subarray ending at i belongs to one of two categories:

• It contains only nums[i].
• It contains an earlier element, so removing nums[i] leaves a nonempty contiguous subarray ending at i - 1.

The best candidate in the second category is dp[i - 1] + nums[i]. Any weaker subarray ending at i - 1 would remain weaker after adding the same value. Taking the maximum of the two possibilities gives the best valid subarray ending at i.

Finally, every valid subarray ends at some index. Therefore, taking the maximum over all dp[i] values gives the best subarray anywhere in the array.

A full DP array is unnecessary because dp[i] depends only on dp[i - 1]. Once the next state has been calculated, older ending states cannot affect future transitions.

So replace:

dp[i - 1] -> current
max(dp[0], ..., dp[i]) -> answer

This is memory compression, not a greedy guess. The state already summarizes every earlier possibility that can influence the next decision.

Invariant: After processing each element, current is the best sum of a nonempty contiguous subarray ending exactly at that element, and answer is the best sum of any nonempty contiguous subarray in the processed prefix.

Implement the nonempty version in Python

Initialize both variables from the first element:

def max_sub_array(nums):
    current = nums[0]
    answer = nums[0]

    for x in nums[1:]:
        current = max(x, current + x)
        answer = max(answer, current)

    return answer

The initialization is part of the correctness proof. It reflects the contract that the chosen subarray must contain at least one element.

A tempting alternative is:

current = 0
answer = 0

That version treats the empty subarray as a candidate with sum 0. It therefore fails on an all-negative input.

You may also see the equivalent update:

current = max(0, current) + x

This says: discard a negative carried sum before adding x. Algebraically, it matches:

max(x, previous_current + x)

But the global answer must still preserve nonempty semantics. The explicit recurrence is usually clearer in an interview because both candidate choices are visible.

I prefer the first implementation when explaining the solution. It exposes the contract directly: take the element alone, or extend the previous valid subarray.

Test the failure cases, not just the happy path

A correct implementation should survive targeted tests that challenge the state meaning.

All-negative input

nums = [-5, -2, -8]

Trace:

Value	Current	Answer
-5	-5	-5
-2	-2	-2
-8	-8	-2

The result is -2, which corresponds to the nonempty subarray [-2].

It must not be 0. Returning 0 means the implementation admitted an empty subarray that the contract forbids.

One element

nums = [7]

Both current and answer start at 7, and the loop has no further work. The result is 7.

This checks that first-element initialization is valid and that no unnecessary empty-input branch has been introduced.

Mixed positive and negative values

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

The answer is 6, from:

[4, -1, 2, 1]

This catches a different misunderstanding: the optimal subarray does not need to contain only positive values. A negative element can remain inside the best segment when extending across it produces a larger total.

All-positive input

nums = [3, 1, 4, 2]

Every extension improves the current sum, so the state grows across the entire array. The answer is 10.

This verifies the other side of the restart decision: do not restart merely because you are scanning; extend when the carried state helps.

The supplied constraints exclude an empty array, so the implementation should not invent a return value for it. If an interviewer changes that contract, clarify whether an empty subarray with sum 0 is allowed before choosing initialization.

Complexity and the reusable recognition rule

The algorithm processes each element once. Each iteration performs a constant number of additions and comparisons:

• Time: O(n)
• Auxiliary space: O(1)

The input array itself is not modified, and only current and answer are retained.

The reusable pattern is broader than this one problem:

If the best valid solution ending at the current position can be derived from the best valid solution ending at the previous position plus the current item, look for a best-ending-here recurrence.

In an interview, use this checklist:

1. Verify whether the candidate must be contiguous.
2. Verify whether the candidate must be nonempty.
3. Write one precise sentence for the ending-here state.
4. Enumerate how a valid solution ending at the current position can be formed.
5. Derive restart versus extend.
6. Initialize from the contract, usually the first element for the nonempty version.
7. Track the best local state and the best global result separately.
8. Test an all-negative array before claiming the solution is finished.
9. Explain that constant space comes from retaining only the previous DP state.

Kadane's algorithm is the compact implementation. The durable skill is the derivation: define what must be true at the current position, preserve the constraint in that state, and let the recurrence carry the proof.