918. Maximum Sum Circular Subarray

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

이어진(Circular) nums 에서 , 그 subarray 의 합이 가장 큰 경우를 구하는 문제이다.

해당 경우는
1.이어지지 않은 부분에 max subarray가 있는 경우
2.이어지는 부분에 있는 경우
: 남아있는 부분은 즉 최소합이 된다. 따라서 전체 합에서 최소합을 빼면 max subarray를 구할 수 있음

로 나누어서 풀 수 있다

class Solution:
    def maxSubarraySumCircular(self, nums: List[int]) -> int:
        if max(nums)<=0:
            return max(nums)
        sum_max = curr_max = sum_min = curr_min = nums[0]

        for i in range(1,len(nums)):
            curr_max = max(nums[i], curr_max+nums[i])
            sum_max=max(curr_max, sum_max)
            curr_min= min(nums[i],curr_min+nums[i])
            sum_min = min(curr_min, sum_min)

        return max(sum_max, sum(nums) - sum_min)