Maximum Subarray Sum

mediumArrays & Hashing+20 XPTime limit 2s

Find the largest possible sum of a non-empty contiguous subarray.

Input:

line 1: n
line 2: n integers

Output: the maximum subarray sum.

Constraints: 1 ≤ n ≤ 2·10⁵, −10⁴ ≤ a[i] ≤ 10⁴. (The answer fits in 64-bit; aim for O(n) — Kadane's algorithm.)

Sample input 1

9
-2 1 -3 4 -1 2 1 -5 4

Sample output 1

Sample input 2

1
-7

Sample output 2

-7

📖 Stuck? Learn the pattern

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…