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]