LC-0918 Medium LeetCode

918. Maximum Sum Circular Subarray

Array Divide and Conquer Dynamic Programming Queue Monotonic Queue

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 47% Topics: Array, Divide and Conquer, Dynamic Programming, Queue, Monotonic Queue

Reading material

Arrays & Hashing 12 min Divide & Conquer 11 min 1-D Dynamic Programming 16 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(1)

class Solution(object):
    def maxSubarraySumCircular(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        total, max_sum, cur_max, min_sum, cur_min = 0, -float("inf"), 0, float("inf"), 0
        for a in A:
            cur_max = max(cur_max+a, a)
            max_sum = max(max_sum, cur_max)
            cur_min = min(cur_min+a, a)
            min_sum = min(min_sum, cur_min)
            total += a
        return max(max_sum, total-min_sum) if max_sum >= 0 else max_sum

Solution from kamyu104/LeetCode-Solutions · MIT