DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Maximum Subarray

mediumArrays and hashing Must-do

Problem statement

You are given a list of integers nums. Find the contiguous run of elements (a "subarray") whose values add up to the largest possible sum, and return that sum.

A subarray must be made of elements that sit next to each other in the original list — you cannot skip elements or reorder them. The list has at least one element, so there is always at least one valid answer (even if every value is negative, the best subarray is just the single largest value).

Think of nums as the profit or loss logged by a service over consecutive time windows (each entry can be positive or negative). This problem asks for the best consecutive stretch — the one where losses are outweighed the most by gains.

Examples

Example 1

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

Output: 6

Explanation: The subarray [4,-1,2,1] has the largest sum, 6. No other contiguous run of elements adds up to more.

Example 2

Input: nums = [1]

Output: 1

Explanation: There is only one element, so the only possible subarray is [1], which sums to 1.

Example 3

Input: nums = [5,4,-1,7,8]

Output: 23

Explanation: Every value here helps the running total more than it hurts it, so the best subarray is the whole array: 5 + 4 - 1 + 7 + 8 = 23.

Hints

Approach

Optimal: Kadane's algorithm

Intuition

At every position, ask one question: is the running subarray sum, extended by this element, better than starting a brand new subarray right here? If the running sum so far is negative, it can only be dragging the total down, so it is never worth carrying forward — better to reset and start fresh from the current element. If the running sum is positive, keep extending it.

This is exactly the "crossing" idea from the divide-and-conquer approach, but done in one direct pass instead of splitting the array — which is what makes it O(n) instead of O(n log n). This is known as Kadane's algorithm.

Steps

  1. Set current and best both to nums[0].
  2. For each remaining element x (starting from index 1):
    • Set current to the larger of x alone, or current + x.
    • If current is greater than best, update best to current.
  3. After the loop, best holds the answer.

Dry run

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

x current = max(x, current + x) best
-2 (start) -2 -2
1 max(1, -2+1=-1) = 1 1
-3 max(-3, 1-3=-2) = -2 1
4 max(4, -2+4=2) = 4 4
-1 max(-1, 4-1=3) = 3 4
2 max(2, 3+2=5) = 5 5
1 max(1, 5+1=6) = 6 6
-5 max(-5, 6-5=1) = 1 6
4 max(4, 1+4=5) = 5 6

The running best peaks at 6, from the subarray [4, -1, 2, 1], matching the expected output.

Edge cases: a single-element list returns that element on the first iteration of the setup step. A list where every value is negative still works — current and best reset to the least negative single element rather than falling to 0, because we never compare against a hard-coded 0.

Complexity

Time O(n) — We look at each element exactly once, doing a constant amount of work per element (one comparison, one addition). There is no nested loop and no recursion, so the cost grows linearly with the size of the input. This is the best possible time complexity, since any correct algorithm must at least look at every element once.

Space O(1) — We only keep two running numbers, the best sum ending at the current position and the best sum seen anywhere so far. Neither grows with the size of the input.

class Solution:
    def maxSubArray(self, nums: list[int]) -> int:
        best = nums[0]
        current = nums[0]
        for x in nums[1:]:
            current = max(x, current + x)
            best = max(best, current)
        return best


if __name__ == "__main__":
    print(Solution().maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))  # 6
    print(Solution().maxSubArray([1]))  # 1
    print(Solution().maxSubArray([5, 4, -1, 7, 8]))  # 23

Follow-up questions

Keep two extra variables, start and bestStart. Whenever you reset current to begin a fresh subarray at index i, set start = i. Whenever current becomes the new best, record bestStart = start and bestEnd = i. This adds two integer variables and no extra passes, so the approach is still O(n) time and O(1) space — you are just remembering where the best sum was found as you go, instead of only what it was.

Yes — Kadane's algorithm already processes the array left to right using only the previous current and best values, so it naturally works as a streaming algorithm. After seeing each new value, update current and best exactly as before and discard the old value; you never need to revisit it. The only change is that "the answer so far" is now a running answer that can be reported at any point in the stream, rather than a single final answer at the end.

RecapThe whole problem in a few lines, for the night before
  • Spot it: "largest sum of a contiguous run" in an array of positive and negative numbers
  • Idea: at each element, decide whether extending the running subarray beats starting a new one there (Kadane's algorithm)
  • Cost: O(n) time, O(1) space (divide and conquer: O(n log n) time, O(log n) space)
  • Trap: trying to skip individual negative numbers instead of comparing "extend vs. restart" at every step — a subarray must stay contiguous

Frequently asked questions

Because "skip the negative number" only works when negatives sit between two separate positive runs, and even then you have to decide whether skipping loses more than it saves. If negatives are mixed among positives (like [4, -1, 2, 1]), keeping the negative can still leave you with a better total than breaking the subarray in two, because a subarray must stay contiguous. Kadane's algorithm handles this correctly by comparing "extend" against "restart" at every step, rather than trying to special-case which negatives to drop.

The answer is the single largest (least negative) value, and every approach above handles this correctly. In Kadane's algorithm, best starts at nums[0] rather than 0, so it never wrongly reports 0 as an achievable sum — a subarray must contain at least one element, and an all-negative array has no way to reach 0.

The same "extend or restart" decision shows up whenever you are scanning a stream of numeric measurements — CPU usage deltas, request latency spikes, or profit and loss per time window — and need to find the worst or best contiguous stretch. Interviewers use Maximum Subarray because it is a clean, fast way to check whether a candidate can turn a vague "find the best window" question into a precise, linear-time algorithm.

Not in plain time complexity — O(n log n) is always slower than O(n) for large inputs. It matters mostly as a building block: some harder problems (like finding the maximum sum rectangle in a 2D matrix) reuse this same "solve each half, then handle the crossing case" idea, so understanding it here pays off later even though the one-pass version wins for this exact problem.