• 1 <= nums.length <= 10⁵
• -10⁴ <= nums[i] <= 10⁴

First, be precise about the word subarray, because interviews are lost on it. A subarray is a contiguous slice of the array: you choose a start position and an end position and take everything between them — no gaps, no reordering. In [5, 4, -1, 7], the slice [4, -1] is a subarray, but [5, 7] is not, because 5 and 7 are not neighbors. (A selection that may skip elements is called a subsequence — a different concept that belongs to different problems.) Our job: among all subarrays containing at least one number, find the one with the largest sum, and return that sum. The "at least one" clause matters: if every number is negative, the right answer is the least negative single element — we are never allowed to answer 0 by taking nothing.

A subarray is pinned down by two choices — where it starts and where it ends. A start at position i can pair with any of the ends at or after it, so an array of N elements has N + (N-1) + ... + 1, roughly N²/2, subarrays. Checking them all is the brute force. One economy is available immediately: holding the start fixed and sliding the end one step right extends the sum by a single addition — no need to re-add the whole window. That brings the cost down to one addition per window: O(N²).

max_sum = nums[0]
for i in range(len(nums)):            # choose where the subarray starts
    current_sum = 0
    for j in range(i, len(nums)):     # slide the end one step at a time
        current_sum += nums[j]        # extend the running sum by one number
        max_sum = max(max_sum, current_sum)
return max_sum

(max(a, b) simply hands back the larger of its two inputs.) At this problem's limit, N = 100,000, that is around five billion additions — far too slow. And the waste has a shape: the same stretches of numbers get re-summed inside many overlapping windows. We want to sweep the array once and never re-add anything.

Here is the thought that cracks the problem open. Every subarray ends somewhere. So imagine we knew, for each position i, the answer to a much smaller question: "among the subarrays that end exactly at position i, which has the largest sum?" The overall winner must be the best of those N answers — every subarray ends at one of the N positions, so none can escape.

And the smaller question turns out to be nearly free to answer. A subarray ending at position i has only two possible shapes: it is the single element nums[i] by itself, or it is some subarray ending at position i - 1 with nums[i] glued on the end. If we are gluing, we should obviously glue onto the best subarray ending at i - 1 — a larger previous sum gives a larger total. Nothing else needs to be considered.

One value flows into the next, so the whole computation is a single pass with two variables.

current_streak = 0                                # best sum ending at the previous position
max_result = nums[0]                              # best answer seen anywhere so far
for x in nums:
    current_streak = max(x, current_streak + x)   # start fresh at x, or extend the streak?
    max_result = max(max_result, current_streak)  # record the best "ending here"
return max_result

Be clear about what each variable means. current_streak is the answer to "best subarray ending right here"; max_result remembers the best of those answers across the whole walk. And note that max_result starts at nums[0], not at 0 — that is what makes the all-negative case come out right. The algorithm is never allowed to pretend an empty subarray with sum 0 exists.

One pass, one addition and two comparisons per element: O(N) time, O(1) extra space — from five billion operations down to a hundred thousand. But the reframe is worth far more than this single problem. Whenever a question asks for the best contiguous stretch of anything, ask: "what is the best stretch ending exactly here, and how does it follow from the one ending one step earlier?" Solving one small question per position, each built from the previous answer, is your first taste of a technique called dynamic programming — and you will meet it again immediately: the very next problem swaps addition for multiplication, and watching exactly where today's reasoning breaks is the whole point of it.