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


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.

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top