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:
Input: nums = [1,-2,3,-2] Output: 3 Explanation: Subarray [3] has maximum sum 3.
Example 2:
Input: nums = [5,-3,5] Output: 10 Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10.
Example 3:
Input: nums = [-3,-2,-3] Output: -2 Explanation: Subarray [-2] has maximum sum -2.
Constraints:
n == nums.length1 <= n <= 3 * 104-3 * 104 <= nums[i] <= 3 * 104The main idea is to use Kadane's Algorithm to find the maximum subarray sum for two scenarios: one, where the subarray wraps around the end and beginning of the array, and two, where it does not.
Calculate the maximum subarray sum using Kadane's algorithm in the normal way. Then calculate the minimum subarray sum using a similar technique but by negating the result. The maximum possible circular subarray sum will be the maximum value between the normal subarray sum and the total array sum minus the minimum subarray sum.
The function kadane is a helper function designed to employ Kadane's algorithm for any iterable. It efficiently finds the maximum sum of a contiguous subarray.
We then calculate the total sum of the array and determine the maximum subarray sum using Kadane's. By reversing the signs of the array elements and applying Kadane's algorithm again, we effectively discover the minimum subarray sum. The maximum sum is then checked against two cases:
C
C++
Java
C#
JavaScript
Time Complexity: O(n) — as both the applications of Kadane's algorithm are linear.
Space Complexity: O(1) — no additional space is used except for a few variables.
Instead of using basic Kadane's approach, we can consider computing the maximum subarray sum with additional memory for storing maximum and minimum values up to each index. This allows precise tracing of subarrays—as contiguous and potential wrap-around cases.
In this dynamic programming approach, two critical values are maintained: the current maximum and minimum subarray sums found. We update each possibility as we iterate across elements and calculate the total array sum to assist in determining potential circular maximum subarrays later.
C
C++
Java
C#
JavaScript
Time Complexity: O(n)
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Kadane's Algorithm for Max Sum and Modified for Min Sum | Time Complexity: O(n) — as both the applications of Kadane's algorithm are linear. Space Complexity: O(1) — no additional space is used except for a few variables. |
| Dynamic Programming Explanation | Time Complexity: O(n) |
Maximum Subarray - Kadane's Algorithm -- Leetcode 53 • Greg Hogg • 366,989 views views
Watch 9 more video solutions →Practice Maximum Sum Circular Subarray with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor