Maximum Sum Circular Subarray

Problem

You are given an integer array nums that is treated as circular: the element after nums[n-1] is nums[0]. Return the largest possible sum of a non-empty subarray, where a subarray is a contiguous run on the circle. A subarray may wrap around the end, but it may not include any index more than once, so its length is at most n.

• nums holds up to about thirty thousand integers, each bounded in magnitude by a few tens of thousands.

Examples

• nums = [2, -4, 6, -4] → 6. The plain subarray [6] is best; wrapping does not help here.
• nums = [8, -6, 8] → 16. Wrap around: [8] + [8] skips the -6 in the middle.
• nums = [-4, -1, -4] → -1. All negative, so the best is the single largest element.

Hints

1. Split the answer into two cases: the best subarray does not wrap, or it does. The first case is ordinary Kadane.
2. If the best subarray wraps around, what does the part of the array it does not cover look like?
3. A wrapping subarray's complement is a non-wrapping subarray, so its sum is total - (minimum subarray sum). Take the max of the two cases, and handle the all-negative array separately.