Taro Logo

Maximum Sum Circular Subarray

Medium
Apple logo
Apple
0 views
Topics:
ArraysDynamic Programming

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.

For example:

  • nums = [1,-2,3,-2] should return 3 because the subarray [3] has the maximum sum of 3.
  • nums = [5,-3,5] should return 10 because the subarray [5,5] has maximum sum 5 + 5 = 10.
  • nums = [-3,-2,-3] should return -2 because the subarray [-2] has maximum sum -2.

What approach would you take to solve this problem, and what is the time and space complexity of your solution?

Solution


Naive Solution

The brute force approach would be to iterate through all possible subarrays and calculate their sums. For a circular array, this involves considering subarrays that wrap around from the end to the beginning. This approach is highly inefficient.

Code (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(1, n + 1):
            current_sum = 0
            for k in range(j):
                index = (i + k) % n
                current_sum += nums[index]
            max_sum = max(max_sum, current_sum)

    return max_sum

Big O Analysis

  • Time Complexity: O(n^2), due to the nested loops.
  • Space Complexity: O(1), as we are only using a constant amount of extra space.

Optimal Solution

The optimal solution involves using Kadane's Algorithm to find the maximum subarray sum and then considering the case where the maximum subarray wraps around. The maximum sum in a circular array can be one of two things:

  1. The maximum subarray sum in the regular array.
  2. The total sum of the array minus the minimum subarray sum.

We use Kadane's algorithm to find both the maximum and minimum subarray sums. The maximum circular subarray sum will be the larger of the maximum subarray sum and the total sum minus the minimum subarray sum. We also handle the case where all numbers are negative, which would result in a total sum equal to the minimum sum. In that case, we simply return the maximum element of the original array.

Code (Python)

def max_subarray_sum_circular(nums):
    n = len(nums)
    max_kadane = kadane(nums)

    total_sum = sum(nums)
    inverted_nums = [-num for num in nums]
    max_circular = total_sum + kadane(inverted_nums)

    if max_circular == 0: # handles edge case, when all numbers are negative
         return max_kadane

    return max(max_kadane, max_circular)


def kadane(nums):
    max_so_far = float('-inf')
    current_max = 0

    for num in nums:
        current_max = max(num, current_max + num)
        max_so_far = max(max_so_far, current_max)

    return max_so_far

Big O Analysis

  • Time Complexity: O(n), as we iterate through the array a constant number of times.
  • Space Complexity: O(1), as we are only using a constant amount of extra space.

Edge Cases

  • Empty array: The problem statement says 1 <= n <= 3 * 10^4 so we don't need to worry about an empty array
  • All negative numbers: If all numbers are negative, the maximum subarray sum will be the largest negative number (least negative). Kadane's algorithm will handle this.
  • All positive numbers: If all numbers are positive, the maximum subarray sum will be the sum of all numbers.
  • Mixed positive and negative numbers: Kadane's algorithm handles this case correctly.