101
0/320
Loading content...
You are given a circular integer array nums containing n elements. Your task is to find and return the maximum possible sum of a non-empty contiguous subarray within this circular arrangement.
A circular array is one where the last element wraps around and connects back to the first element. Formally, for any element at index i, its next element is at index (i + 1) % n, and its previous element is at index (i - 1 + n) % n. This circular nature allows subarrays to wrap around from the end of the array to the beginning.
A subarray is a contiguous sequence of elements from the array. In this circular context, a subarray may span from some index to the end of the array and continue from the beginning, but each individual element from the underlying array can only be included at most once in any valid subarray. Formally, for a subarray spanning positions i, i+1, ..., j (with wraparound), there must not exist any k1 and k2 within the subarray range such that k1 % n == k2 % n (meaning the same original index is used twice).
Your goal is to identify the contiguous subarray (which may or may not wrap around) that yields the highest possible sum among all valid subarrays.
nums = [1,-2,3,-2]3The subarray [3] has the maximum sum of 3. Even though the array is circular, the best subarray in this case does not need to wrap around. Taking just the element 3 gives us the optimal result.
nums = [5,-3,5]10The circular subarray [5,5] wraps around from the last element to the first element, giving us 5 + 5 = 10. This is achieved by taking the last element (5) and the first element (5), skipping the middle element (-3). This demonstrates the power of the circular structure.
nums = [-3,-2,-3]-2When all elements are negative, we must still return a non-empty subarray. The optimal choice is the single element [-2], which has the maximum sum of -2 among all possible subarrays. Taking multiple negative elements would only decrease the sum further.
Constraints