Maximum Circular Subarray Sum
mediumArrays & Prefix Sums+20 XPTime limit 2s
The array is arranged in a circle: after the last element comes the first one again. A subarray may wrap around the end, but it may not use any element twice. Find the largest possible sum of a non-empty subarray.
Input:
- line 1:
n - line 2:
nintegers
Output: the maximum circular subarray sum.
Constraints: 1 ≤ n ≤ 10⁵, −10⁴ ≤ a[i] ≤ 10⁴.
Think about it: the best subarray either doesn't wrap (plain Kadane) or wraps — and a wrapping subarray is everything except one middle block, so its sum is total − (minimum subarray sum). Take the larger of the two. Watch out when every number is negative: then "everything except the minimum" would be empty.
Sample input 1
5 5 -3 5 -2 1
Sample output 1
9
Sample input 2
3 -3 -2 -1
Sample output 2
-1
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).