Maximum Sum Circular Subarray
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.