[카데인 Kadane] 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)

 

최종 코드

 

순환 행렬일때는

1) 모두 음수면(연속행렬 전체합==연속행렬 최소합): "연속 행렬 최대합"

2) 모두 음수가 아니면: "연속행렬 전체합 - 연속 행렬 최소합" 와  "연속 행렬 최대합" 중 최대값

 

✅ 문제 핵심 정리

nums가 원형(circular)이기 때문에 가능한 subarray는 2가지 유형이 있어요:

1. 한 번만 순회하는 일반적인 subarray
   → Kadane 알고리즘 그대로 적용 (max_kadane)
2. 끝에서 시작으로 연결된 원형 subarray
   → 전체합에서 최솟값 subarray를 빼면 됨 (total_sum - min_kadane)

class Solution:
    def maxSubarraySumCircular(self, nums: List[int]) -> int:
        # 연속 행렬 최대 합 => 카데인 Kadane 알고리즘        
        len_n = len(nums)
        
        maxSum = nums[0]
        curMaxSum = 0

        minSum = nums[0]
        curMinSum = 0

        totalSum = 0
        for n in nums:
            totalSum += n

            curMaxSum = max(curMaxSum, 0)
            curMaxSum += n
            maxSum = max(maxSum, curMaxSum)

            curMinSum = min(curMinSum, 0)
            curMinSum += n
            minSum = min(minSum, curMinSum)

        # 전체가 음수일 경우에는 totalSum == minSum → maxSum 반환
        if totalSum == minSum:
            return maxSum
        else:
            return max(maxSum, totalSum - minSum)