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?
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.
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
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:
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.
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
1 <= n <= 3 * 10^4
so we don't need to worry about an empty array