[LeetCode] 918. Maximum Sum Circular Subarray

- Problem

918. Maximum Sum Circular Subarray

- 내 풀이

class Solution:
    def maxSubarraySumCircular(self, nums: List[int]) -> int:
        N = len(nums)
        dp = [[0 for _ in range(N)] for _ in range(2)]
        dp[0][0] = dp[1][0] = nums[0]

        for i in range(1, N):
            dp[0][i] = min(dp[0][i-1] + nums[i], nums[i], 0)
            dp[1][i] = max(dp[1][i-1] + nums[i], nums[i], 0)
            
        min_sum = min(dp[0])
        max_sum = max(dp[1])

        return max(sum(nums)-min_sum, max_sum) if max_sum > 0 else max(nums)

- 결과

• 시간 복잡도: O(N)
• 공간 복잡도: O(N)

- refactoring code

class Solution:
    def maxSubarraySumCircular(self, nums: List[int]) -> int:
        cur_min = cur_max = total = 0
        min_sum = max_sum = nums[0]

        for i in range(len(nums)):
            cur_min = min(cur_min + nums[i], nums[i])
            min_sum = min(min_sum, cur_min)

            cur_max = max(cur_max + nums[i], nums[i])
            max_sum = max(max_sum, cur_max)

            total += nums[i]

        answer = max(max_sum, total - min_sum)

        return [max(nums), answer][answer > 0]

• 시간 복잡도: O(N)
• 공간 복잡도: O(1)

- 결과