leetcode：918. Maximum sum of circular subarray [reverse thinking + maximum subarray sum]

analysis

This question If it is not a ring, the normal subarray is OK If you find out maxn Less than 0, All negative numbers , Just go back
otherwise Start thinking about having rings , It's one end at a time , Then you need the least in the middle , So it's the minimal array and
And then use sum Just subtract it

ac code

class Solution:
    def maxSubarraySumCircular(self, nums: List[int]) -> int:
        #  acyclic ： Normal maximum subarray and 
        maxn = -inf
        now = 0
        for num in nums:
            now += num
            maxn = max(maxn, now)
            now = max(0, now)
        
        if maxn < 0:
            return maxn #  All negative numbers 
        
        #  Ring ： Normal minimal arrays and 
        minn = inf
        now = 0
        for num in nums:
            now += num
            minn = min(minn, now)
            now = min(0, now)
        
        #  The maximum value in a ring without a ring 
        return max(maxn, sum(nums) - minn)

summary

Thinking questions