Find the largest possible sum of a contiguous, non-empty run of numbers.
Input
Line 1: an integer n.
Line 2: n integers (which may be negative).
Output
The maximum sum over all contiguous non-empty subarrays.
Maximum Subarray Sum
Mediumarraysdynamic-programming
Examples
Example 1
- Input
9 -2 1 -3 4 -1 2 1 -5 4
- Output
6
The run [4, -1, 2, 1] sums to 6, the maximum.
Example 2
- Input
1 5
- Output
5
A single element.
Example 3
- Input
4 -1 -2 -3 -4
- Output
-1
All negative — the best single element is -1.
Constraints
- 1 <= n <= 10^5
- -10^4 <= each number <= 10^4
Hints
Reveal hint 1
A subarray either extends the best run ending at the previous element, or starts fresh at the current one.
Reveal hint 2
Kadane's algorithm tracks the best sum ending here and the best seen overall in a single pass.
Reference solution (spoiler — try it yourself first)
Approach
Kadane's algorithm: cur = max(x, cur + x) for each element; best = max(best, cur). Handles all-negative arrays because the run must be non-empty.
import sys
d = list(map(int, sys.stdin.read().split()))
n = d[0]
a = d[1:1 + n]
best = cur = a[0]
for x in a[1:]:
cur = max(x, cur + x)
best = max(best, cur)
print(best)
Bring us the problem, not a perfect specification
Tell us what needs to change, who it affects and any important deadline. We will review the context and reply with useful next questions.
- 01Share contextDescribe the workflow, constraint or risk.
- 02Clarify togetherWe identify missing facts and useful options.
- 03Choose a startAgree a focused assessment or delivery step.