Maximum Sum Circular Subarray

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.length
• 1 <= n <= 3 * 10^4
• -3 * 10^4 <= nums[i] <= 3 * 10^4

# Circular Subarray Maximum Sum

This problem asks us to find the maximum sum of a non-empty subarray in a circular integer array. A circular array means the end connects to the beginning.  We need to consider two cases: the maximum subarray is within the array, or it wraps around.

## 1. Naive Approach (Brute Force)

We can iterate through all possible subarrays and compute their sums, keeping track of the maximum sum found so far. This involves considering all possible starting and ending points for the subarrays, handling the circular nature by using modulo arithmetic.

```python
def max_subarray_sum_circular_brute_force(nums):
    n = len(nums)
    max_sum = -float('inf')
    
    for i in range(n):
        for j in range(n):
            current_sum = 0
            for k in range(i, i + j + 1):
                current_sum += nums[k % n]
            max_sum = max(max_sum, current_sum)
            
    return max_sum

Example:

nums = [1, -2, 3, -2]
max_subarray_sum_circular_brute_force(nums)  # Output: 3

Big(O) Analysis

• Time Complexity: O(n^3) - Three nested loops.
• Space Complexity: O(1) - Constant extra space.

2. Optimal Solution (Kadane's Algorithm + Total Sum - Minimum Sum)

The optimal solution involves using Kadane's algorithm to find the maximum subarray sum within the array. Then, we find the minimum subarray sum and subtract it from the total sum of the array. The larger of these two values (max subarray sum and total sum - min subarray sum) will be our answer.

Algorithm:

1. Find the maximum subarray sum using Kadane's algorithm.
2. Find the minimum subarray sum using a modified Kadane's algorithm.
3. Calculate the total sum of the array.
4. Return the maximum of (maximum subarray sum, total sum - minimum subarray sum). Handle the case where all elements are negative.

def max_subarray_sum_circular(nums):
    n = len(nums)
    total_sum = sum(nums)

    # Kadane's Algorithm to find maximum subarray sum
    max_so_far = 0
    current_max = 0
    for x in nums:
        current_max = max(x, current_max + x)
        max_so_far = max(max_so_far, current_max)

    # Kadane's Algorithm to find minimum subarray sum
    min_so_far = 0
    current_min = 0
    for x in nums:
        current_min = min(x, current_min + x)
        min_so_far = min(min_so_far, current_min)

    # Handle the case where all elements are negative
    if max_so_far == 0:
        return max(nums)

    return max(max_so_far, total_sum - min_so_far)

Example:

nums = [5, -3, 5]
max_subarray_sum_circular(nums)  # Output: 10

Big(O) Analysis

• Time Complexity: O(n) - Single pass through the array for each Kadane's algorithm and sum calculation.
• Space Complexity: O(1) - Constant extra space.

Edge Cases

1. All Negative Numbers: If all numbers are negative, the maximum subarray sum is the largest negative number (least negative).
2. All Positive Numbers: The maximum subarray sum is the sum of all numbers.
3. Empty Array: The problem statement specifies a non-empty array, but handling it would require a check at the start.

def max_subarray_sum_circular_handle_empty(nums):
    if not nums:
        return 0  # Or raise an exception
    return max_subarray_sum_circular(nums)

1. Large Numbers: The sums could potentially overflow. Consider using a larger data type (e.g., long in Java, int64 in Python).

Code with edge case handling and overflow consideration:

def max_subarray_sum_circular_robust(nums):
    n = len(nums)
    total_sum = 0
    max_so_far = -float('inf')
    current_max = 0
    min_so_far = float('inf')
    current_min = 0

    for x in nums:
        total_sum += x
        current_max = max(x, current_max + x)
        max_so_far = max(max_so_far, current_max)
        current_min = min(x, current_min + x)
        min_so_far = min(min_so_far, current_min)

    if max_so_far < 0:
        return max_so_far  # All numbers are negative

    return max(max_so_far, total_sum - min_so_far)

This robust version handles edge cases where all numbers are negative and uses -float('inf') and float('inf') to correctly initialize max_so_far and min_so_far.