918. Maximum Sum Circular Subarray

918. Maximum Sum Circular Subarray

 

내 코드

class Solution:
    def maxSubarraySumCircular(self, nums: List[int]) -> int:
        maxSum = nums[0]
        curSum = 0
        
        for n in range(len(nums)*2):
            if curSum <0:
                curSum = 0

            curSum += nums[n%len(nums)]
            maxSum = max(maxSum, curSum)

        return maxSum

 

이 코드는 틀렸음. 

%  모듈러 연산으로 회전 행렬을 반영하고 있으나.

행렬 길이를 고려하고 있지 않음.

 

class Solution:
    def maxSubarraySumCircular(self, nums: List[int]) -> int:
        maxSum = nums[0]
        curSum = 0

        l = 0 # 윈도우의 왼쪽 포인터
        
        for r in range(len(nums)*2):
            # if curSum <0:
            #     curSum = 0

            curSum += nums[r%len(nums)]

            if r-l+1 > len(nums): # 행렬크기 넘어가면
                curSum -= nums[l%len(nums)]
                l+=1

            if nums[l%len(nums)] < 0:
                curSum -= nums[l%len(nums)]
                l+=1
            
            maxSum = max(maxSum, curSum)

        return maxSum

 

고려해봤는데,

오답입..ㅠㅠ

 

https://youtu.be/fxT9KjakYPM?si=rsJ9Sk4RQcDyVVhV

 

 

class Solution:
    def maxSubarraySumCircular(self, nums: List[int]) -> int:
        # Kadane's Algorithm
        # maximum subarry sum = sigma(nums) - minimum subarry sum
        #                     = total - global minimum
        globalMax, globalMin = nums[0], nums[0]
        curMax, curMin = 0, 0
        total = 0

        for n in nums:
            curMax = max(curMax + n, n)
            curMin = min(curMin + n, n)
            total += n
            globalMax = max(globalMax, curMax)
            globalMin = min(globalMin, curMin)

        # 전체 배열이 최소 합일 경우, 원형 배열 고려 불가
        # 모든 행렬의 요소가 음수 일 경우
        if total == globalMin:
            return globalMax

        # 최대값은 직선 최대 부분 배열 합과 원형 최대 부분 배열 합 중 더 큰 값
        return max(globalMax, total-globalMin)