[Python] Leetcode 918. Maximum Sum Circular Subarray (Medium)

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

Maximum Sum Circular Subarray - LeetCode

Maximum Subarray를 살짝 비튼 문제입니다.

처음엔 Maximum Subarray를 앞 뒤로 두번 구해서 겹치지 않도록 조각을 붙여가며 탐색할까 생각도 해봤지만 깔끔한 구현방법이 떠오르지 않아서 솔루션을 참고했습니다.

생각지도 못했던 아이디어가 있더라구요.

 

https://leetcode.com/problems/maximum-sum-circular-subarray/discuss/178422/One-Pass

One Pass - LeetCode Discuss

 

자세한 설명은 위 링크에 있는데 핵심 아이디어는 이미지만 봐도 알 수 있으실것 같습니다.

 

자명하게도 최대합이 되는 부분수열은 두 경우중에 하나일겁니다.

원형으로 이어지지 않거나, 이어지거나.

이어지지 않는 경우는 기존의 Maximum Subarray문제의 풀이와 같습니다.

이어지는 경우는 위 그림처럼 전체 합에서 Minimum Subarray를 뺀 값이 됩니다.

 

 

다시 생각해보면 원형으로 이어진 이 Maximum Subarray는 아래의 array의 Maximum Subarray와 같습니다.

(왼쪽 부분을 똑 떼어서 붙였습니다.)

array를 두 부분으로 나누었을 때, 한쪽이 최대합이라면 반대쪽은 최소합이 됩니다.

totalSum - maxSum = minSum / totalSum - minSum = maxSum

만약 더 작은 음수의 다른 minSum이 존재한다면 maxSum도 더 큰 수가 생겨서 수식에 모순이 생기게 됩니다.

array의 모든 수가 양수여서 minSum이 없는 경우에는 배열의 전체 totalSum이 문제의 해답이 되고, 케이스 1에서 찾아낼 수 있습니다.

 

즉 array의 minSum을 찾아 totalSum에서 뺀다면 원형으로 이어진 maxSum을 알아낼 수 있습니다.

minSum을 찾는 메소드를 따로 작성해도 되지만 기존의 메소드를 이용하되 입력 배열의 부호를 바꿔주면 똑같이 구할 수 있습니다. 다만 모든 수가 음수인 경우(minSum == totalSum)에는 예외가 발생하므로 그 부분만 따로 처리해주시면 됩니다.

 

class Solution:
    def maxSubarraySumCircular(self, nums: list) -> int:
        nonCircularSum = self.maxSubArray(nums)
        circularSum = sum(nums)
        
        for i in range(0,len(nums)):
            nums[i] = -nums[i]
        
        circularSum += self.maxSubArray(nums)
        
        return max(nonCircularSum,circularSum) if(circularSum != 0) else nonCircularSum
    
    def maxSubArray(self, nums: list) -> int:
        sum = -100_000
        maxSum = -100_000
        for i in nums:
            if(i > i + sum):
                sum = i
            else:
                sum += i
                
            maxSum = max(sum, maxSum)
                
        return maxSum

input = [[1,-2,3,-2],[5,-3,5],[-3,-2,-3]]
for i in input:
    print(Solution().maxSubarraySumCircular(i))