leetcode：918. 环形子数组的最大和【逆向思维 + 最大子数组和】

分析

这道题 如果不是环形的话就正常子数组就可以了 如果求出来的maxn是小于0，那全部负数，直接返回即可
否则 开始考虑有环的，就是一头一尾的，那么就需要中间最少，那么就是最小子数组和
然后用sum减掉就可以

ac code

class Solution:
    def maxSubarraySumCircular(self, nums: List[int]) -> int:
        # 无环：正常最大子数组和
        maxn = -inf
        now = 0
        for num in nums:
            now += num
            maxn = max(maxn, now)
            now = max(0, now)
        
        if maxn < 0:
            return maxn # 全是负数
        
        # 有环：正常最小子数组和
        minn = inf
        now = 0
        for num in nums:
            now += num
            minn = min(minn, now)
            now = min(0, now)
        
        # 有环无环中的最大值
        return max(maxn, sum(nums) - minn)

总结

思维题