Maximum Subarray
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

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
- Can the subarray be empty? (Here: no, at least one element. That changes the all-negative answer.)
- Do you need the sum or the indices? (Here: the sum; the indices are a common follow-up.)
- Can the array be empty? (Here: no.)
- Could the sum overflow? With n = 10⁵ and values up to 10⁴, it fits in 32 bits; bigger inputs need 64-bit.
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.