You are given a circular integer array nums
of length n
. Your task is to find and 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 3
.nums = [5,-3,5]
should return 10
because the subarray [5,5]
has the maximum sum 5 + 5 = 10
.nums = [-3,-2,-3]
should return -2
because the subarray [-2]
has the maximum sum -2
.Describe an algorithm to efficiently solve this problem. Consider both the time and space complexity of your solution.
The most straightforward approach is to generate all possible subarrays and compute their sums, keeping track of the maximum sum encountered. Since the array is circular, we need to consider subarrays that wrap around. This involves iterating through all possible start indices and lengths of subarrays.
i
from 0
to n-1
.i
, iterate through all possible lengths len
from 1
to n
.i
with length len
, considering the circular nature of the array.def max_subarray_sum_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):
index = (i + k) % n
current_sum += nums[index]
max_sum = max(max_sum, current_sum)
return max_sum
We can solve this problem efficiently by combining Kadane's algorithm with the consideration of circular subarrays.
total_sum - min_subarray_sum
. This is because subtracting the minimum subarray from the total sum leaves the maximum sum of the remaining elements, which form the circular subarray.total_sum - min_subarray_sum
might be 0, which is incorrect. We should return the maximum of the Kadane's algorithm result and the circular subarray sum, handling cases where Kadane's algorithm returns the correct answer.total_sum - min_subarray_sum
is zero and all elements in the array are negative, we must return the largest negative number. We can use the maxSubarraySum which is Kadane's algorithm for this.def max_subarray_sum_circular(nums):
n = len(nums)
# Kadane's Algorithm for max subarray sum
def kadane(arr):
max_so_far = float('-inf')
current_max = 0
for x in arr:
current_max = max(x, current_max + x)
max_so_far = max(max_so_far, current_max)
return max_so_far
# Kadane's Algorithm for min subarray sum
def min_kadane(arr):
min_so_far = float('inf')
current_min = 0
for x in arr:
current_min = min(x, current_min + x)
min_so_far = min(min_so_far, current_min)
return min_so_far
max_subarray_sum = kadane(nums)
min_subarray_sum = min_kadane(nums)
total_sum = sum(nums)
# Handle edge case where all elements are negative
if total_sum == min_subarray_sum:
return max_subarray_sum
circular_max_sum = total_sum - min_subarray_sum
return max(max_subarray_sum, circular_max_sum)