Max Circular Subarray Sum

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() <= 10⁵
-10⁴ <= arr[i] <= 10⁴

Approach 01:

#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.