Maximum Subarray
FreeGreedyMedium61 of 75
The problem
Find the greatest sum of a nonempty contiguous subarray within a nonempty integer array.
Example
[-3, 4, -1, 2, -6] → 5, from [4, -1, 2]
Need a hint?
A negative running prefix can only hurt the next segment.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Track the best sum ending at the current position. Either start over at x or extend the previous segment with x, whichever is larger. Update a global best after each step. Initialize from the first element to handle all-negative arrays.
Complexity
O(n) time and O(1) extra space.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.