Skills101
← All coding problems

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: n integers

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).

Loading editor…

Log in to run and submit your code — it's free.