Circular Max Subarray
MediumDynamic Programming · Amazon
You are given an integer array nums that is circular: the element after nums[n - 1] is nums[0]. Return the largest possible sum of a non-empty contiguous subarray.
A subarray may wrap around the end, for example nums[n - 2], nums[n - 1], nums[0], nums[1], but it may include each position at most once, so it is never longer than n.
Aim for O(n) time.
Example 1
- Input:
- nums = [10,-12,11]
- Output:
- 21
- Explanation
- Wrapping wins: taking 11 at the end and continuing around to 10 at the start gives 21. The best run that does not wrap is just
[11].
Example 2
- Input:
- nums = [3,-1,2,-1]
- Output:
- 4
- Explanation
- The best run is
[3, -1, 2]with sum 4. Wrapping to also take the trailing -1 would only lower it.
Example 3
- Input:
- nums = [-4,-2,-7]
- Output:
- -2
- Explanation
- Every value is negative, but the subarray must be non-empty, so the best choice is the single largest value, -2.
Constraints
1 <= nums.length <= 3 * 10^4-3 * 10^4 <= nums[i] <= 3 * 10^4