#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/google-interview-prep-v2/coding-patterns-i-arrays-strings-hash-maps/lc-918-maximum-sum-circular-subarray-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/google-interview-prep-v2/coding-patterns-i-arrays-strings-hash-maps/lc-918-maximum-sum-circular-subarray-implementation

Repovive

LeetCode 918 Maximum Sum Circular Subarray - Implementation - Coding Patterns I: Arrays, Strings & Hash Maps | Google Interview Prep | Repovive

Repovive.

Google Interview Prep6 sections · 128 units7h total

Open in Course

LeetCode 918 Maximum Sum Circular Subarray - Implementation

The code

Run max-Kadane and min-Kadane simultaneously. Handle the all-negative edge case.

function maxSubarraySumCircular(nums):
    totalSum = 0
    maxSum = nums[0]
    curMax = 0
    minSum = nums[0]
    curMin = 0
    for num in nums:
        curMax = max(curMax + num, num)
        maxSum = max(maxSum, curMax)
        curMin = min(curMin + num, num)
        minSum = min(minSum, curMin)
        totalSum += num
    if maxSum < 0:
        return maxSum
    return max(maxSum, totalSum - minSum)

$O(n)$ time, $O(1)$ space.