leetcode: Maximum Sum Circular Subarray (kadane 알고리즘)

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

 

해당 문제는 kadane 알고리즘 방법으로 접근하여 문제를 해결 하였습니다.

 

Approach

 

• Kadane's algorithm을 사용하여 일반적인 최대 부분합을 O(n)에 구합니다.
• 순환하는 경우는 전체 합에서 최소 부분합을 빼서 구합니다.
• 모든 원소가 음수인 경우는 별도로 처리합니다.

시간복잡도: O(n) 공간복잡도: O(1)

1. 전체 배열의 합 (total): 5 + (-3) + 5 = 7
2. 최소 부분합 (minSum): -3
   • 연속된 부분 배열 중 가장 작은 합
3. total - minSum = 7 - (-3) = 10
   • 이것이 바로 [5,5]를 선택했을 때의 합과 같습니다!

이렇게 되는 이유는:

1. 순환 배열에서 양 끝의 원소들을 선택하려면 (예: [5,5])
2. 중간에 있는 원소들을 제외해야 합니다 (예: [-3])
3. 중간의 원소들을 제외하는 가장 좋은 방법은 "최소 부분합"을 찾아서 제거하는 것입니다
4. 따라서 "전체 합 - 최소 부분합"이 순환 배열에서 가능한 최대 부분합이 됩니다

이 방식은 다음과 같은 장점이 있습니다:

• 한 번의 순회로 최소 부분합을 찾을 수 있습니다 (O(n))
• 전체 합도 한 번의 순회로 구할 수 있습니다 (O(n))
• 추가 메모리를 사용하지 않습니다 (O(1))

 

 

 

func maxSubarraySumCircular(nums []int) int {
	if len(nums) == 0 {
		return 0
	}

	kadane := func(nums []int, findMax bool) int {
		curr := nums[0]
		result := nums[0]

		for i := 1; i < len(nums); i++ {
			if findMax {
				curr = max(nums[i], curr+nums[i])
				result = max(curr, result)
			} else {
				curr = min(nums[i], curr+nums[i])
				result = min(curr, result)
			}
		}
		return result
	}

	findMax := kadane(nums, true)
	if findMax < 0 {
		return findMax
	}

	totalSum := 0

	for _, num := range nums {
		totalSum += num
	}

	findMin := kadane(nums, false)
	return max(findMax, totalSum-findMin)
}