918. Maximum Sum Circular Subarray

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

先看Leetcode 53 Maximum Subarray

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        currSum = 0
        maxSum = float("-inf")
        for num in nums:
            currSum = max(currSum+num, num)
            maxSum = max(maxSum, currSum)
        return maxSum

这道题只需要讨论两个情况：

(1) max subarray

(2) total - min subarray

唯一的corner case，当所有数是负数时，最后结果max subarray是array里面的最大值

class Solution:
    def maxSubarraySumCircular(self, A: List[int]) -> int:
        currMax = 0
        maxSum = float("-inf")
        currMin = 0
        minSum = float("inf")
        total = 0
        
        for num in A:
            currMax = max(num,num+currMax)
            maxSum = max(maxSum,currMax)
            currMin = min(num,num + currMin)
            minSum = min(currMin,minSum)
            total += num
        if minSum == total:
            return maxSum
        return max(maxSum, total- minSum)