Largest Sum Subarray in a Circular Array
Implement maxCircularSubarraySum
Given a CIRCULAR array
nums — where the last element connects back around to the first — return the largest possible sum of any non-empty contiguous subarray, allowing the subarray to wrap past the end of the array and continue from the beginning.
Trying every wrapped window works, but re-summing each one from scratch wastes the structure of the problem. Every wrap-around subarray is the complement of some ordinary, non-wrapping subarray sitting in the middle — so the best wrap-around sum is just total - (the minimum-sum subarray). Running Kadane's algorithmKadane's AlgorithmA single O(n) pass that finds the maximum-sum contiguous subarray by tracking a running "best streak ending here," resetting it to the current element whenever extending the previous streak would hurt rather than help. twice — once for the maximum, once for the minimum — turns an O(n²) search into a single O(n) pass.
Example 1:
Input: nums = [5,-3,5]
Output: 10
Example 2:
Input: nums = [1,-2,3,-2]
Output: 3
Example 3:
Input: nums = [-3,-2,-3]
Output: -2
+ 7 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ nums.length ≤ 3×10⁴ - ●
-3×10⁴ ≤ nums[i] ≤ 3×10⁴
nums =
[5, -3, 5]