Circular Subarray Maximum Sum

Problem Description

Given a circular integer array nums of length n, the goal is to find the maximum possible sum of a non-empty subarray of nums. A circular array means the end connects to the beginning. Each element can only be included once in any subarray.

Naive Solution

A brute-force approach would involve iterating through all possible subarrays and computing their sums, keeping track of the maximum sum encountered. Since the array is circular, we need to consider subarrays that wrap around.

1. Iterate through each starting index i from 0 to n-1.
2. For each starting index i, iterate through all possible lengths len from 1 to n.
3. Compute the sum of the subarray starting at i with length len, handling the circular nature of the array using the modulo operator.
4. Keep track of the maximum sum found so far.

Code (Python):

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

Time Complexity: O(n^2), due to the nested loops.

Space Complexity: O(1), as we only use a constant amount of extra space.

Optimal Solution

Kadane's Algorithm provides an efficient way to solve this problem.

The central idea is:

1. Find the maximum subarray sum using Kadane's algorithm (standard, non-circular).
2. Find the minimum subarray sum using Kadane's algorithm.
3. The maximum circular subarray sum is either the maximum subarray sum from step 1 or the total sum of the array minus the minimum subarray sum from step 2.
4. Handle the edge case where all elements are negative (in which case, the maximum sum is the largest single element).

Algorithm:

1. Calculate the maximum subarray sum (max_kadane): Apply Kadane's algorithm to find the maximum sum of a contiguous subarray in the standard way.
2. Calculate the minimum subarray sum (min_kadane): Apply Kadane's algorithm, but track the minimum sum instead of the maximum.
3. Calculate the total sum of the array (total_sum).
4. Calculate the maximum circular subarray sum:
   • max_circular = total_sum - min_kadane.
5. Return the maximum of max_kadane and max_circular.
6. Edge Case: if all numbers are negative, max_kadane will be the largest number, and total_sum - min_kadane will be zero. To handle this, if max_kadane is negative and is the total sum, then return max_kadane. If the max_kadane is equal to the total sum, it means we've considered the entire array, which invalidates the circularity aspect when we subtract min_kadane from the total sum. So we need to return max_kadane in that case.

Code (Python):

def kadane(nums):
    max_so_far = float('-inf')
    current_max = 0
    
    for x in nums:
        current_max = max(x, current_max + x)
        max_so_far = max(max_so_far, current_max)
    
    return max_so_far


def min_kadane(nums):
    min_so_far = float('inf')
    current_min = 0

    for x in nums:
        current_min = min(x, current_min + x)
        min_so_far = min(min_so_far, current_min)

    return min_so_far


def max_subarray_circular(nums):
    n = len(nums)
    max_kadane_sum = kadane(nums)
    min_kadane_sum = min_kadane(nums)
    total_sum = sum(nums)

    if max_kadane_sum < 0: # All numbers are negative, return max
      return max_kadane_sum

    max_circular = total_sum - min_kadane_sum

    return max(max_kadane_sum, max_circular)

Time Complexity: O(n), as Kadane's algorithm takes O(n) time, and we perform it twice.

Space Complexity: O(1), as we only use a constant amount of extra space.

Edge Cases

• All negative numbers: If the array contains only negative numbers, the maximum subarray sum will be the largest single element (i.e., the element with the smallest absolute value). Kadane's algorithm handles this case correctly.
• All positive numbers: If the array contains only positive numbers, the maximum subarray sum will be the sum of all elements.
• Mixed positive and negative numbers: Kadane's algorithm correctly handles the general case of mixed positive and negative numbers.
• Empty array: The problem statement specifies a non-empty array. An empty array is not a valid input.