Maximum Subarray

Free with account Updated Nov 19, 2026 · 4 min read
On this page

    Problem statement

    Given an array of integers, find the contiguous subarray (at least one element) with the largest sum, and return that sum. The numbers can be negative.

    Kadane's algorithm in one question. It shows up as "best stretch of daily profit", "strongest streak of scores", and inside many DP problems. Original problem: LeetCode 53.

    Example

    The best run is 4, −1, 3: the −1 is worth keeping because the 3 after it more than makes up for it.
    The best run is 4, −1, 3: the −1 is worth keeping because the 3 after it more than makes up for it.
    Input:  [3, -5, 4, -1, 3, -6, 2]
    Output: 6          # 4 + (-1) + 3
    Input:  [-3, -1, -2]
    Output: -1         # every run is negative; the best is the single largest number

    Constraints (assumed)

    • 1 ≤ n ≤ 10⁵; −10⁴ ≤ value ≤ 10⁴.
    • The subarray must contain at least one element.

    What this question tests

    • Finding the right DP state: the best sum of a run that ends at index i.
    • Reducing that DP to two variables (Kadane's algorithm).
    • Handling the all-negative case correctly.

    Questions to ask first

    1. Can the subarray be empty? (Here: no, at least one element. That changes the all-negative answer.)
    2. Do you need the sum or the indices? (Here: the sum; the indices are a common follow-up.)
    3. Can the array be empty? (Here: no.)
    4. Could the sum overflow? With n = 10⁵ and values up to 10⁴, it fits in 32 bits; bigger inputs need 64-bit.