Solution For Maximum Sum Circular Subarray

The Maximum Sum Circular Subarray problem on LeetCode can be solved using the Kadane’s algorithm and a little bit of modification to handle the circular subarray case. The problem statement is as follows:

Given a circular integer array nums of length n, return the maximum possible sum of a non-empty subarray of nums.

Example:

Input: [1,-2,3,-2] Output: 3
Explanation: Subarray [3] has maximum sum 3

Algorithm:

1. Find the maximum subarray sum using Kadane’s algorithm. This will give the maximum sum when there are no circular shifts.

2. Find the minimum subarray sum using the same algorithm but by negating the array elements. This will give us the minimum sum when there are no circular shifts.

3. Compute the total sum of the array.

4. Compute the circular sum by subtracting the minimum sum from the total sum. This will give us the maximum sum when there is one circular shift.

5. Return the maximum of step 1 and step 4.

Pseudo code:

def maxSubarraySumCircular(nums):
max_sum = nums[0] min_sum = nums[0] curr_max = nums[0] curr_min = nums[0] total_sum = nums[0] n = len(nums)

# Compute the maximum and minimum subarray sums
for i in range(1, n):
    curr_max = max(curr_max + nums[i], nums[i])
    max_sum = max(max_sum, curr_max)

    curr_min = min(curr_min + nums[i], nums[i])
    min_sum = min(min_sum, curr_min)

    total_sum += nums[i]

# Compute the circular sum
circular_sum = total_sum - (-min_sum) # Negate min_sum to convert it to max_sum

# Return the maximum of normal and circular subarray sums
return max(max_sum, circular_sum)

Time complexity: O(n)

Space complexity: O(1)

Step by Step Implementation For Maximum Sum Circular Subarray

class Solution {
    public int maxSubarraySumCircular(int[] A) {
        int total = 0;
        int maxSum = Integer.MIN_VALUE;
        int currMax = 0;
        int minSum = Integer.MAX_VALUE;
        int currMin = 0;
        for (int a : A) {
            currMax = Math.max(currMax + a, a);
            maxSum = Math.max(maxSum, currMax);
            currMin = Math.min(currMin + a, a);
            minSum = Math.min(minSum, currMin);
            total += a;
        }
        return maxSum > 0 ? Math.max(maxSum, total - minSum) : maxSum;
    }
}

class Solution:
    def maxSubarraySumCircular(self, A: List[int]) -> int:
        # kadane's algorithm to find maximum subarray sum
        # for a given array
        max_sum = A[0]
        curr_max = A[0]
        
        for i in range(1, len(A)):
            curr_max = max(A[i], curr_max + A[i])
            max_sum = max(max_sum, curr_max)
            
        # for minimum subarray sum
        min_sum = A[0]
        curr_min = A[0]
        
        for i in range(1, len(A)):
            curr_min = min(A[i], curr_min + A[i])
            min_sum = min(min_sum, curr_min)
            
        # in case all values in the array are negative
        if max_sum == min_sum:
            return max_sum
        
        # otherwise return maximum of maximum subarray sum
        # found by kadane's algorithm and total sum - minimum
        # subarray sum
        return max(max_sum, sum(A) - min_sum)

var maxSubarraySumCircular = function(A) {
    let N = A.length

    let ans = A[0], cur = A[0]
    for (let i = 1; i < N; ++i) {
        cur = A[i] + Math.max(cur, 0)
        ans = Math.max(ans, cur)
    }

    // ans is the answer for 1-interval subarrays.
    // Now, let's consider all 2-interval subarrays.
    // For each i, we want to know
    // the maximum of sum(A[j:]) with j >= i+2

    // rightsums[i] = A[i] + A[i+1] + ... + A[N-1]
    let rightsums = new Array(N).fill(0)
    rightsums[N-1] = A[N-1]
    for (let i = N-2; i >= 0; --i)
        rightsums[i] = rightsums[i+1] + A[i]

    // maxright[i] = max_{j >= i} rightsums[j]
    let maxright = new Array(N).fill(0)
    maxright[N-1] = A[N-1]
    for (let i = N-2; i >= 0; --i)
        maxright[i] = Math.max(maxright[i+1], rightsums[i])

    let leftsum = 0
    for (let i = 1; i < N-1; ++i) {
        leftsum += A[i-1]
        ans = Math.max(ans, leftsum + maxright[i+1])
    }

    return ans
};

class Solution {
public:
    int maxSubarraySumCircular(vector& A) {
        int total = 0, maxSum = -30000, curMax = 0, minSum = 30000, curMin = 0;
        for (int a : A) {
            curMax = max(curMax + a, a);
            maxSum = max(maxSum, curMax);
            curMin = min(curMin + a, a);
            minSum = min(minSum, curMin);
            total += a;
        }
        return maxSum > 0 ? max(maxSum, total - minSum) : maxSum;
    }
};

public int MaxSubarraySumCircular(int[] A) {
        //Kadane's algorithm to find maximum sum subarray
        int max_so_far = A[0], max_ending_here = A[0]; 
        for (int i = 1; i < A.Length; i++) 
        { 
            /* Find maximum sum subarray having start and 
               end indices as i and j */
            max_ending_here = Math.Max(max_ending_here + A[i], A[i]); 
            /* Update result if this sum is found to be maximum so far */
            if (max_so_far < max_ending_here) 
                max_so_far = max_ending_here; 
        } 
        //In case all numbers are negative, return maximum of the array
        if (max_so_far < 0)
            return max_so_far;
        //Otherwise, return maximum sum of a non-empty subarray
        int max_wrap = 0, min_wrap = 0;
        for (int i = 0; i < A.Length; i++)  
        { 
            max_wrap += A[i]; 
            min_wrap += A[i]; 
            A[i] = -A[i]; 
        } 
        //max sum with corner elements will be: 
        //array-sum - (-max subarray sum of A)
        max_wrap = max_wrap + MaxSubarraySumCircular(A); 
        //Similarly, calculate minimum sum subarray (Needs 
        //to be done as second step as we have modified original 
        //array) 
        MinSubArraySum(A); 
        min_wrap = min_wrap + min_wrap_sum; 
        //The maximum circular sum will be maximum of two sums
        return (max_wrap > min_wrap)? max_wrap: min_wrap; 
    } 
    static int min_wrap_sum = int.MaxValue; 
    //utility function to find minimum sum subarray
    static void MinSubArraySum(int []arr) 
    { 
        //Kadane's algorithm to find minimum sum subarray
        int min_so_far = arr[0], min_ending_here = arr[0]; 
        for (int i = 1; i < arr.Length; i++)  
        { 
            /* Find minimum sum subarray having start and 
               end indices as i and j */
            min_ending_here = Math.Min(min_ending_here + arr[i], arr[i]); 
            /* Update result if this sum is found to be minimum so far */
            if (min_so_far > min_ending_here) 
                min_so_far = min_ending_here; 
        } 
        min_wrap_sum = min_so_far; 
    }