918.Maximum_Sum_Circular_Subarray(Medium).md

918. Maximum Sum Circular Subarray (Medium)

Date and Time: Jan 22, 2025, 22:34 (EST)

Link: https://leetcode.com/problems/maximum-sum-circular-subarray

Question:

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.

Example 1:

Input: nums = [1,-2,3,-2]

Output: 3

Explanation: Subarray [3] has maximum sum 3.

Example 2:

Input: nums = [5,-3,5]

Output: 10

Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10.

Example 3:

Input: nums = [-3,-2,-3]

Output: -2

Explanation: Subarray [-2] has maximum sum -2.

Constraints:

• n == nums.length

• 1 <= n <= 3 * 10^4

• -3 * 10^4 <= nums[i] <= 3 * 10^4

Walk-through:

Notice that, if we find a globalMin (no matter a single element or a subarray), the rest of the the subarray will be or include the maximum from nums. So everytime, we use the Kadane's algorithm to update curMin, curMax and globalMin and globalMax. Finally, we return the maximum of either globalMax or sum(nums) - globalMin.

Python Solution:

class Solution:
    def maxSubarraySumCircular(self, nums: List[int]) -> int:
        # TC: O(n), n=len(nums), SC: O(1)
        # Use kadane's alg to update curMin and curMax
        curMax = curMin = 0
        globalMax = globalMin = 0
        # if all elements are negative, return the max negative element
        if max(nums) < 0:
            return max(nums)
        for n in nums:
            curMax = max(n, curMax + n)
            globalMax = max(curMax, globalMax)
            curMin = min(n, curMin + n)
            globalMin = min(globalMin, curMin)
        return max(globalMax, sum(nums) - globalMin)

Time Complexity: $O(n)$
Space Complexity: $O(1)$