PythonMediumDynamic Programming20 min
Find the maximum contiguous subarray sum
The array contains at least one integer. For all-negative arrays, choose the largest individual value rather than an empty subarray. Interviewers use this problem to assess track the best sum ending at the current position.
Input
First line: n. Second line: n space-separated integers (empty when n = 0).
Output
Print the result on one line; print an empty line for an empty string.
Constraints
1 <= n <= 100000; -10^9 <= values <= 10^9.
Example
Input
9 -2 1 -3 4 -1 2 1 -5 4
Output
6
Example 2 input
3 1000000000 1000000000 -1
Output
2000000000
The sum can exceed a signed 32-bit integer.
Public test cases (2)
Input
9 -2 1 -3 4 -1 2 1 -5 4
Expected output
6
Input
3 -5 -2 -8
Expected output
-2
Hints (2)
- Identify the state needed to avoid repeated work.
- Track the best sum ending at the current position.
Target complexity: time O(n) · space O(1)