Maximum Sum Circular Subarray

Reported in interviews at Citi GTS

Problem statement

You are given an array $a_1, a_2, \ldots, a_n$ of integers, which may include negative values. A circular subarray is a contiguous slice that may wrap around -- that is, it can include a suffix of the array followed by a prefix. For example, in $[1, -2, 3, -1, 4]$, the circular subarray $[4, 1]$ (the last element followed by the first) has sum $5$.

Design an algorithm to find the maximum sum over all non-empty circular subarrays, running in $O(n)$ time and $O(1)$ space.

Constraints:

  • $1 \leq n \leq 10^5$
  • $-10^4 \leq a_i \leq 10^4$
  • The subarray must be non-empty
  • Your algorithm must handle the edge case where all $a_i < 0$

Examples:

Example 1:

  • Input: $[1, -2, 3, -1, 4]$
  • Output: $7$
  • Explanation: The best non-circular subarray is $[3, -1, 4]$ with sum $6$, but the circular subarray $[3, -1, 4, 1]$ (the suffix $3, -1, 4$ followed by the prefix $1$) has sum $7$. Maximum is $7$.

Example 2:

  • Input: $[5, -3, 5]$
  • Output: $10$
  • Explanation: The circular subarray $[5, 5]$ (last + first) has sum $10$.

Example 3:

  • Input: $[-3, -2, -1]$
  • Output: $-1$
  • Explanation: All values are negative; the best we can do is take the single largest element $-1$.
Show hint

If a slice wraps around the end, what does the part it leaves out look like?

Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems