Kadane's Algorithm for Circular Subarrays

Hello! In our previous lessons, we thoroughly explored Kadane's algorithm, first understanding its core logic and then extending it to find the start and end indices of the maximum subarray. You now have a solid foundation for this powerful technique.

Today, we'll apply this knowledge to a more complex and interesting variant: the maximum circular subarray sum. Your goal is to learn how to adapt Kadane's algorithm to solve this problem, which is a classic interview question that tests your ability to break down a problem and reuse existing patterns. This involves a clever insight that builds directly on what we've already learned.

The Two Cases of a Circular Subarray

When an array is circular, it means the end connects to the beginning. This introduces a new possibility for what a "subarray" can be. The maximum sum subarray will fall into one of two distinct categories:

1. A non-wrapping subarray: The subarray is a single contiguous block, just like in the standard maximum subarray problem. For example, in [1, -2, 3, 4, -5], the subarray [3, 4] is a non-wrapping subarray. We already know how to find the best one of these using Kadane's algorithm.

2. A wrapping subarray: The subarray consists of elements from the end of the array combined with elements from the beginning. For example, in [5, -3, -2, 5], the subarray [5, 5] (wrapping around) has a sum of 10.

This is visualized perfectly in the diagram below.

The Key Insight: Inverting the Problem

Handling Case 1 is straightforward—it's just Kadane's algorithm. The trick is how to handle Case 2 efficiently.

Instead of trying to find the sum of a wrapping subarray directly, let's think about what's left out. A wrapping subarray that takes elements from the prefix and suffix of the array necessarily leaves out a contiguous block of elements in the middle. To maximize the sum of the wrapping parts, we must minimize the sum of the part we leave out.

This leads to the central insight of the problem:

Maximum Sum of a Wrapping Subarray = (Total Sum of the Array) - (Minimum Sum of a Non-Wrapping Subarray)

Let's look at a concrete example.

So, our overall strategy is:

1. Calculate the maximum sum for a non-wrapping subarray (Case 1). Let's call this max_sum_kadane.
2. Calculate the maximum sum for a wrapping subarray (Case 2). This is total_sum - min_sum_kadane.
3. The final answer is the greater of these two values.

This approach is elegantly explained in the following video.

The Algorithm: One Pass to Rule Them All

We need three values to find our solution:

• The maximum subarray sum (max_sum_kadane).
• The minimum subarray sum (min_sum_kadane).
• The total sum of the array (total_sum).

Remarkably, we can find all of these in a single pass. We already know how to find max_sum_kadane using Kadane's algorithm. To find min_sum_kadane, we can apply the exact same logic but in reverse: instead of maximizing the running sum, we minimize it.

The algorithm is as follows:

1. Initialize variables:
   • global_max, current_max for Kadane's max algorithm.
   • global_min, current_min for Kadane's min algorithm.
   • total_sum.
2. Iterate through the array once. In each step:
   • Update current_max and global_max.
   • Update current_min and global_min.
   • Add the current element to total_sum.
3. After the loop, calculate the potential answer from the wrapping case: max_wrap = total_sum - global_min.
4. The final result seems to be max(global_max, max_wrap). However, there's a critical edge case to consider first.

The Edge Case: All Negative Numbers

What happens if all the numbers in the array are negative, for example, [-5, -2, -3]?

• total_sum = -10
• global_max (from Kadane's) = -2 (the subarray [-2])
• global_min (from reversed Kadane's) = -10 (the subarray [-5, -2, -3])

If we apply our formula, max_wrap = total_sum - global_min = -10 - (-10) = 0.
The final answer would be max(global_max, max_wrap) = max(-2, 0) = 0.

This is incorrect. The problem specifies a non-empty subarray, so we cannot get a sum of 0 from an all-negative array. The correct answer is -2.

This issue occurs only when all numbers are negative. In this situation, the minimum subarray is the entire array itself, so total_sum - global_min becomes total_sum - total_sum, which is 0. This incorrectly represents the sum of an empty subarray.

The Fix:
A simple check resolves this. If global_max is less than 0, it means every element in the array must have been negative (otherwise global_max would be at least 0). In this specific situation, the wrapping case calculation is invalid, and the answer must be the non-wrapping global_max.

The complete logic is:

1. Calculate global_max, global_min, and total_sum in a single pass.
2. If global_max < 0, return global_max.
3. Otherwise, return max(global_max, total_sum - global_min).

This logic is concisely summarized in the following resources.

Implementation in Python

Here is a Python implementation that puts all these pieces together.

def max_subarray_sum_circular(nums):
    if not nums:
        return 0

    total_sum = 0
    



    # Kadane's for maximum subarray sum
    global_max = float('-inf')
    current_max = 0
    



    # Kadane's for minimum subarray sum
    global_min = float('inf')
    current_min = 0

    for num in nums:



        # Update for max sum
        current_max += num
        if current_max > global_max:
            global_max = current_max
        if current_max < 0:
            current_max = 0
            



        # Update for min sum
        current_min += num
        if current_min < global_min:
            global_min = current_min
        if current_min > 0:
            current_min = 0
            



        # Update total sum
        total_sum += num




    # This is a slightly different implementation of Kadane's that might fail for all-negative arrays.
    # A more robust single-pass Kadane's would be:
    # current_max = max(num, current_max + num)
    # global_max = max(global_max, current_max)
    # The code below uses a more direct and robust implementation.
    



    # Let's use a cleaner, single-pass implementation
    g_max, c_max = nums[0], nums[0]
    g_min, c_min = nums[0], nums[0]
    total = nums[0]

    for i in range(1, len(nums)):
        num = nums[i]
        c_max = max(num, c_max + num)
        g_max = max(g_max, c_max)
        
        c_min = min(num, c_min + num)
        g_min = min(g_min, c_min)
        
        total += num




    # Handle the all-negative edge case
    # If g_max < 0, all numbers are negative. The answer is just g_max.
    # Another way to check this is if the total sum equals the global minimum.
    # This means the minimum subarray is the entire array.
    if g_max < 0: # or `if total == g_min:`
        return g_max
    
    return max(g_max, total - g_min)




# Example 1:
nums1 = [1, -2, 3, 4, -5]



# global_max = 7 ([3, 4])
# global_min = -5 ([-5])
# total_sum = 1
# max_wrap = 1 - (-5) = 6 ([1, -2, 3, 4])
# result = max(7, 6) = 7
print(f"Result for {nums1}: {max_subarray_sum_circular(nums1)}") # Expected: 7




# Example 2:
nums2 = [5, -3, 5]



# global_max = 7 ([5, -3, 5])
# global_min = -3 ([-3])
# total_sum = 7
# max_wrap = 7 - (-3) = 10 ([5, 5])
# result = max(7, 10) = 10
print(f"Result for {nums2}: {max_subarray_sum_circular(nums2)}") # Expected: 10




# Example 3 (Edge Case):
nums3 = [-3, -2, -1]



# global_max = -1
# This triggers the edge case `if g_max < 0`, so it returns -1.
print(f"Result for {nums3}: {max_subarray_sum_circular(nums3)}") # Expected: -1

Given your interest in finance, you can think of this problem as an extension of analyzing stock returns. The standard Kadane's finds the most profitable continuous period to hold a stock. The Kadane's for the minimum finds the worst continuous period (i.e., when you'd lose the most). The circular problem asks: is it better to find one great period to invest (non-wrapping case), or is the stock so bad during a specific period that it's more profitable to invest outside of that period (wrapping case)?

Conclusion

You have now learned how to tackle a significant variation of the maximum subarray problem by applying a clever "inversion" technique. This demonstrates a key problem-solving skill: transforming an unfamiliar problem into one you already know how to solve.

Key Takeaways:

• The maximum circular subarray is either non-wrapping or wrapping.
• The non-wrapping case is solved by the standard Kadane's algorithm.
• The wrapping case is solved by inverting the problem: Total Sum - Minimum Subarray Sum.
• The minimum subarray sum can also be found using a variation of Kadane's algorithm.
• A critical edge case occurs when all numbers are negative, which would incorrectly yield a result of 0. This is handled by checking if the non-wrapping maximum is negative.

This lesson concludes our deep dive into core subarray techniques using prefix sums and Kadane's algorithm. You've built a strong foundation for recognizing and solving a wide range of array-based problems.

In our next module, we will explore a completely different, yet equally fundamental, array pattern: the two-pointer technique. We'll begin by using it to solve array partitioning problems like the famous Dutch National Flag problem.