Given an array of integers arr[] in a circular fashion. Find the maximum subarray sum that we can get if we assume the array to be circular.
Examples:
Input: arr[] = [8, -8, 9, -9, 10, -11, 12] Output: 22 Explanation: Starting from the last element of the array, i.e, 12, and moving in a circular fashion, we have max subarray as 12, 8, -8, 9, -9, 10, which gives maximum sum as 22.
Input: arr[] = [10, -3, -4, 7, 6, 5, -4, -1] Output: 23 Explanation: Maximum sum of the circular subarray is 23. The subarray is [7, 6, 5, -4, -1, 10].
Input: arr[] = [-1, 40, -14, 7, 6, 5, -4, -1]
Output: 52 Explanation: Circular Subarray [7, 6, 5, -4, -1, -1, 40] has the maximum sum, which is 52.
Constraints:
1 <= arr.size() <= 105
-104 <= arr[i] <= 104
Approach 01:
-
C++
-
Python
#include <vector> #include <algorithm> #include <numeric> #include <climits> using namespace std; class Solution { public: int circularSubarraySum(vector<int>& arr) { int n = arr.size(); int totalSum = accumulate(arr.begin(), arr.end(), 0); // Calculate total sum of the array int maxSubarraySum = INT_MIN; // Initialize with the smallest integer int minSubarraySum = INT_MAX; // Initialize with the largest integer int currentMax = 0, currentMin = 0; for (int num : arr) { // Kadane's algorithm for maximum subarray sum currentMax = max(num, currentMax + num); maxSubarraySum = max(maxSubarraySum, currentMax); // Kadane's algorithm for minimum subarray sum currentMin = min(num, currentMin + num); minSubarraySum = min(minSubarraySum, currentMin); } // Handle the circular case int circularMax = (minSubarraySum != totalSum) ? totalSum - minSubarraySum : INT_MIN; return max(maxSubarraySum, circularMax); } };
def circularSubarraySum(arr): n = len(arr) totalSum = sum(arr) # Calculate the total sum in one go maxSubarraySum = float("-inf") # Initialize with negative infinity minSubarraySum = float("inf") # Initialize with positive infinity # Kadane's algorithm for maximum subarray sum currentMax = 0 currentMin = 0 for num in arr: currentMax = max(num, currentMax + num) maxSubarraySum = max(maxSubarraySum, currentMax) currentMin = min(num, currentMin + num) minSubarraySum = min(minSubarraySum, currentMin) # Handle the circular case circularMax = totalSum - minSubarraySum if minSubarraySum != totalSum else float("-inf") return max(maxSubarraySum, circularMax)
Time Complexity
- Kadane’s Algorithm:
Both the maximum and minimum subarray sums are calculated using Kadane’s algorithm, which involves a single iteration over the array. This takes \( O(n) \) time.
- Total Sum:
The total sum of the array is calculated using the `accumulate` function, which also takes \( O(n) \) time.
- Overall Time Complexity:
\( O(n) \) for processing the array in a single pass.
Space Complexity
- Auxiliary Variables:
Constant space is used to store variables like `totalSum`, `maxSubarraySum`, `minSubarraySum`, `currentMax`, `currentMin`, and loop variables. This requires \( O(1) \) space.
- Input Array:
The input array is used only for iteration, and no additional space is allocated for it. This does not count towards extra space usage.
- Overall Space Complexity:
\( O(1) \) since no additional space proportional to the input size is used.