Problem Statement in English

You’re given an array nums. Your task is to find the subarray with maximum sum, except the subarray can be circular. So for example, given nums = [5,-3,-1,4], your answer is $9$, since [4,5] is a valid circular subarray.

Approach

This builds on another post where we used Kadane’s Algorithm. The only catch here, is that the subarray can be circular. The approach to this is very clever, yet really simple.

Kadane’s Algorithm is able to find the max subarray in the middle of the array. Think about it.

But if the solution is a circular sum, then it’s unable to find that. So instead, what if you modify the algorithm to look for the smallest sum subarray instead? This way you can subtract that value from the sum of the array, and that should give you the subarray with largest circular sum!

Here’s an example: nums = [5,-1,4]. The smallest subarray sum is $-1$, and the total sum of the array is $8$. When you subtract them, you get $8- (-1) = 9$, which is the answer.

Solution in Python


class Solution:
    def maxSubarraySumCircular(self, nums: List[int]) -> int:
        bestMax = nums[0]
        currentSum = 0

        for i in range(len(nums)):
            currentSum = max(currentSum, 0)
            currentSum += nums[i]
            bestMax = max(currentSum, bestMax)

        # at this point we have the best regular sum
        # but what about a circular sum

        # so we find the smallest regular sum
        bestMin = nums[0]
        currentSum = 0

        for i in range(len(nums)):
            currentSum = min(currentSum, 0)
            currentSum += nums[i]
            bestMin = min(bestMin, currentSum)

        # total sum of the array
        totalSum = sum(nums)

        bestCircularSum = totalSum - bestMin

        return max(bestMax, bestCircularSum) if (bestCircularSum != 0) else bestMax

Complexity

  • Time: $O(n)$
    Since we iterate over $n$ elements at most.

  • Space: $O(1)$
    Since we only use a couple integer variables.

Mistakes I Made

I tried using modulo arithmetic to aid in the circular case.

And we are done.