Maximum Sum Circular Subarray
Problem Description
Given a circular integer array nums of length n, return the maximum possible sum of a non-empty subarray of nums.
A circular array means the end of the array connects to the beginning of the array. Formally, the next element of nums[i] is nums[(i + 1) % n] and the previous element of nums[i] is nums[(i - 1 + n) % n].
A subarray may only include each element of the fixed buffer nums at most once. Formally, for a subarray nums[i], nums[i + 1], ..., nums[j], there does not exist i <= k1, k2 <= j with k1 % n == k2 % n.
Example 1:
Explanation: Subarray [3] has maximum sum 3.
Example 2:
Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10.
Example 3:
Explanation: Subarray [-2] has maximum sum -2.
Constraints:
- n == nums.length
- 1 <= n <= 3 * 104
- -3 * 104 <= nums[i] <= 3 * 104
Solve it on LeetCode
Approaches
1. Kadane's Algorithm
Intuition:
The basic approach to solve the Maximum Subarray Sum problem can be achieved by using Kadane's Algorithm. However, this problem introduces a circular array aspect: that is, the end of the array wraps around to the start. We need to find the maximum subarray in two scenarios: one without the wrapping, and one where the subarray might wrap around the end of the array back to the beginning.
Steps:
- Without Circularity: Use Kadane's algorithm to find the maximum subarray sum that does not wrap around (the traditional approach).
- Handle Wrap-around: The other possible case is that the maximum subarray wraps around the circle. This can be handled by considering the total array sum minus the minimum subarray sum (found via Kadane's applied to the negative values).
- Handle the edge case where all numbers are negative: in this case, the maximum subarray is just a single (least negative) number, so we should not consider wrapping.
Code:
- Time Complexity: O(N), where N is the number of elements in the array, due to single pass traversal.
- Space Complexity: O(1), as no extra space is utilized.