hardDynamic Programming 1DPure DSA~35 min
Maximum Subarray Sum on a Circular Buffer
Readings are stored in a circular ring buffer, so a contiguous window may wrap from the end back to the start. Find the maximum sum of any non-empty contiguous window.
Problem
Given a circular integer array nums, return the maximum possible sum of a non-empty subarray. A circular subarray may wrap from the end to the beginning, but no element is used more than once.
Input
An integer array nums interpreted circularly.
Output
An integer: the maximum circular subarray sum.
Constraints
- 1 <= nums.length <= 3*10^4
- -3*10^4 <= nums[i] <= 3*10^4
- The subarray must be non-empty.
Examples
Example 1
Input
nums = [1,-2,3,-2]
Output
3
The best window is [3].
Example 2
Input
nums = [5,-3,5]
Output
10
Wrapping window [5,5] sums to 10.