[LeetCode] Maximum Absolute Sum of any SubArray (Python)

Problem

 

Solution

Kadane's algorithm

subArray 중 절대값 합의 최대값을 구하는 문제.

2중포문으로 구현하면 당연히 time limit 이 발생한다.

힌트 중에서 Kadane's 알고리즘을 사용하라고한다. 알아보았더니 dp 문제였다.

Kadane's 알고리즘을 간략히 설명하면

• 일반적인 Kadane’s Algorithm은 최대 연속 부분합을 구하는 알고리즘입니다.
• 여기서는 최대 합과 최소 합을 동시에 추적하여, 그 절댓값 중 가장 큰 값을 반환하도록 변경합니다.
• 현재까지의 max_sum/min_sum 을 현재 num과 비교하며 갱신한다.

Kadane's 알고리즘 설명은 다른 블로그 설명을 참고했다.

https://scavienger.tistory.com/19

[Algorithm] Kadane's Algorithm

 

Code

- 2중 for문으로 구현

class Solution:
    def maxAbsoluteSum(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return abs(nums[0])

        max_sum = float('-inf')
        for i in range(len(nums)):
            current_sum = 0
            for j in range(i, len(nums)):
                current_sum += nums[j]
                max_sum = max(max_sum, abs(current_sum))
        return max_sum

 

- Kadane's Algorithm

class Solution:
    def maxAbsoluteSum(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return abs(nums[0])

        answer = 0
        current_max = 0
        current_min = 0

        for num in nums:
            # 최대 합을 구하는 Kadane's Algorithm
            current_max = max(num, current_max + num)
            # 최소 합을 구하는 Kadane's Algorithm
            current_min = min(num, current_min + num)
                
            # 최대 절댓값을 추적
            answer = max(answer, abs(current_max), abs(current_min))

        return answer

 

Complexity

Time Complexity

for문으로 배열 1번 순회 => O(N)

 

Space Complexity

상수만 사용 => O(1)