Maximum Sum Circular Subarray Leetcode Problem 918 [Python Solution]

With a greedy algorithms, we will solve the Maximum Sum Circular Subarray Leetcode problem which has been encountered in interviews by companies such as Microsoft.

In this guide, we’ll dive deep into understanding the problem, explore the constraints, and provide both a brute-force and an efficient solution in Python.

Problem Overview

The problem statement for the Maximum Sum Circular Subarray goes as follows:

Given a circular integer array nums of length n, your task is to return the maximum possible sum of a non-empty subarray of nums.

A circular array implies that 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 should not exist i <= k1, k2 <= j with k1 % n == k2 % n.

Let’s illustrate this problem with a few examples:

Example 1:

Input: nums = [1,-2,3,-2]
Output: 3
Explanation: The subarray [3] has the maximum sum, which is 3.

Example 2:

Input: nums = [5,-3,5]
Output: 10
Explanation: The subarray [5,5] has the maximum sum of 5 + 5 = 10.

Example 3:

Input: nums = [-3,-2,-3]
Output: -2
Explanation: The subarray [-2] has the maximum sum, which is -2.

Constraints:

n == nums.length
1 <= n <= 3 * 10^4
-3 * 10^4 <= nums[i] <= 3 * 10^4

Now, let’s dive deeper into understanding the constraints of this problem.

Understanding the Constraints

Before we proceed to explore the solutions, it’s essential to understand the constraints set by the problem:

The input array nums has a length of n, which is constrained to be between 1 and 30,000. This implies that our solution should be efficient and not involve nested loops that result in high time complexity.
The values in the nums array can range from -30,000 to 30,000. This range is crucial for our algorithm design, as it affects how we handle different elements in the array.

Now that we’ve grasped the problem statement and constraints, let’s explore two approaches to solve it: the brute-force approach and a more efficient one.

Brute-Force Approach

To tackle the Maximum Sum Circular Subarray problem, we’ll start with a straightforward brute-force approach.

This method will help us understand the problem better and will serve as a reference point when we develop a more efficient solution.

Pseudo Code:

globMax, curMax = nums[0], nums[0]


for i, n in enumerate(nums):
    # Update the current maximum
    curMax = max(curMax + n, n)

    # Update the global maximum
    globMax = max(curMax, globMax)


return globMax

In this approach, we initialize two variables, globMax and curMax, both set to the first element of the input array nums.

We then iterate through the array, updating the current maximum (curMax) by comparing the sum of the current element and the current maximum with the element itself.

We also update the global maximum (globMax) during each iteration to track the maximum subarray sum encountered so far.

Finally, we return the global maximum as the result, which represents the maximum subarray sum within the given array.

Efficient Approach

The brute-force approach mentioned above is a good starting point, but we can optimize our solution to achieve better time complexity.

This efficient approach aims to find the maximum circular subarray sum by considering both circular and non-circular subarrays.

Python Code Solution:

View on GitHub ➹

def maxSubarraySumCircular(self, nums: List[int]) -&gt; int:
    # Initialize variables for global maximum and minimum
    globMax, globMin = nums[0], nums[0]
    # Initialize variables for current maximum and minimum
    curMax, curMin = 0, 0
    # Initialize a variable to calculate the total sum of the array
    total = 0

    # Iterate through the input array
    for i, n in enumerate(nums):
        # Update the current maximum
        curMax = max(curMax + n, n)
        # Update the current minimum
        curMin = min(curMin + n, n)
        # Calculate the total sum of the array
        total += n
        # Update the global maximum
        globMax = max(curMax, globMax)
        # Update the global minimum
        globMin = min(curMin, globMin)

    # Return the maximum of two possible results:
    # 1. The global maximum (non-circular subarray)
    # 2. The total sum minus the global minimum (circular subarray)
    return max(globMax, total - globMin) if globMax &gt; 0 else globMax

In this efficient approach, we start by initializing variables for the global maximum (globMax), global minimum (globMin), current maximum (curMax), and current minimum (curMin).

Additionally, we keep track of the total sum of the input array using the total variable.

We then iterate through the input array, updating curMax and curMin based on the current element and previous calculations.

We also update globMax and globMin as we progress through the array.

The key to solving this problem efficiently is recognizing that the maximum circular subarray sum can be either the maximum non-circular subarray sum (represented by globMax) or a circular subarray sum.

The circular subarray sum can be computed as the total sum of the array minus the minimum circular subarray sum (represented by globMin).

We handle this case in the last line of the code.

We check whether globMax is greater than zero.

If it is, we return the maximum of globMax and the circular subarray sum (total minus globMin).

If globMax is not greater than zero, it means that all elements in the array are negative.

In this case, the circular subarray sum would also be zero, so we return globMax as the result.

This efficient approach provides a solution to the Maximum Sum Circular Subarray problem with a time complexity of O(n) and constant space complexity.

Time and Space Complexity

To summarize the time and space complexity of our efficient solution:

Time Complexity: O(n)
We iterate through the input array once, making a constant number of comparisons and updates in each iteration.
Space Complexity: O(1)
We use a fixed number of variables to keep track of the maximum, minimum, and total values, resulting in constant space usage.

Now that we’ve explored both the brute-force and efficient approaches to solving the Maximum Sum Circular Subarray problem, let’s conclude our discussion.

Reasoning Behind Our Approach

In this problem-solving guide, we’ve examined the Maximum Sum Circular Subarray problem, discussed its constraints, and provided both a brute-force and an efficient approach in Python.

The brute-force approach serves as a clear starting point, allowing us to understand the problem thoroughly.

It involves a simple iteration through the input array, continuously updating the maximum subarray sum.

While this approach provides a solution, it’s not the most efficient.

Our efficient approach optimizes the solution, considering both non-circular and circular subarrays.

It utilizes four variables to keep track of maximum and minimum values and the total sum of the array.

By iterating through the array and updating these variables, we can find the maximum circular subarray sum with a time complexity of O(n).

In conclusion, we’ve provided a comprehensive solution to the Maximum Sum Circular Subarray problem, catering to beginners and those preparing for coding interviews.

This guide allows you to grasp the problem, explore different approaches, and understand the reasoning behind the efficient solution.

For further practice and exploration, you can visit the LeetCode problem description to solve the problem and test your understanding.

If you found this guide helpful, please like, engage, and feel free to ask questions, make suggestions, or share your thoughts in the comments.

Happy coding, and best of luck with your problem-solving journey!