JavaMediumDynamic Programming20 min
Find the maximum contiguous subarray sum
Print the largest sum of any nonempty contiguous subarray. Follow the stated ordering and edge-case conventions exactly. Interviewers use this task to probe algorithm selection, invariants, and boundary handling.
Input
n followed by n integers.
Output
Print the largest sum of any nonempty contiguous subarray.
Constraints
1 <= n <= 100000; values in [-1000000000,1000000000].
Example
Input
9 -2 1 -3 4 -1 2 1 -5 4
Output
6
Example 2 input
5 1 -1 1 -1 1
Output
1
This example exercises a further boundary or ordering case.
Public test cases (2)
Input
9 -2 1 -3 4 -1 2 1 -5 4
Expected output
6
Input
3 -4 -2 -9
Expected output
-2
Hints (2)
- Identify the state needed to avoid recomputing work for each element.
- Kadane's recurrence either extends the best suffix or starts a new one at the current element.
Target complexity: time O(n) · space O(1)