Return the largest sum of a non-empty contiguous subarray.
Before you code
The best subarray ending at i either starts fresh at i or extends the best subarray ending at i − 1.
Hints
cur = max(x, cur + x);best = max(best, cur).- Initialize with the first element, not 0, so all-negative arrays work.
- Follow-up: divide and conquer gives O(n log n) and generalizes to segment trees.
Production & complexity notes
When solving Maximum subarray on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in One-dimensional problems to reinforce the underlying pattern.
What it practices
States that end exactly at a position, from One-dimensional problems.