[LeetCode] 53. Maximum Subarray

*알고리즘 스터디에 참여하면서 Blind 75 LeetCode Questions 목록에 있는 문제를 풀이합니다. 

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

Maximum Subarray - LeetCode

 

문제 해설

입력 값으로 nums 라는 배열이 들어오고, 배열에는 최소 하나의 정수가 존재한다.
배열 원소들 중 연속되는 subarray의 합이 최대가 되는 값을 찾아 return 해야 한다.

예를 들어, 
입력값으로 [ -2, 1, -3, 4, -1, 2, 1, -5, 4 ] 가 들어오면 
subarray 중 [4, -1, 2, 1]의 합이 6으로 합이 가장 크기 때문에 6을 return 하면 된다.

 

---

 

풀이 - (1) Brute Force

2중 for 문을 이용해서 가장 큰 합을 찾아 return 한다. 시간 복잡도는 O(N\(^{2}\))이다.

 

---

 

풀이 - (2) Dynamic Programming 

Kadane's Algorithm을 이용한다.

자세한 개념 내용은 [DP - Kadane's Algorithm] 블로그 포스팅을 참고해주세요. 

출처: Rohit Singhal, https://zrr.kr/TuBd

요약해서 설명하자면
배열 i 번째 인덱스에 위치한 원소를 시작으로 첫번째 원소로 이동하면서 subarray 값을 구하는데,
위의 예시와 같이 배열 i-1번째 인덱스에 위치한 원소를 기준으로 구했던 subarray 합들의 최대값을 알고 있다면,
추가된 i번째 배열값을 포함한 subarray 합만 비교하면 최대값을 구할 수 있다. 
즉, max(nums[i], Local_Maximum[i-1] + nums[i]) 가 우리가 찾는 답이 될 것이다. 

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        maxLocal = maxSub = nums[0]
        
        for num in nums[1:]:
            maxLocal = max(num, maxLocal + num)
            maxSub = max(maxLocal, maxSub)
        
        return maxSub

Brute Force와 달리 배열을 한번만 순회하면 되기 때문에 시간복잡도는 O(N)이다. 

 

---

 

풀이 - (3) Dvide and Conquer

이 문제에서는 그다지 효율적이지 않은 방법이지만, 알고리즘 공부를 위해 풀이해본다.
Divide and Conquer를 사용하는 대표적인 알고리즘은 Merge Sort 와 Quick Sort가 있다. 

분할 정복 알고리즘을 이 문제에 적용하면 총 세가지 결과값을 비교하면 된다.

배열의 가운데 원소를 기준으로,
1) 왼쪽에서부터 max_subarray
2) 오른쪽에서부터 max_subarray
3) 왼쪽, 오른쪽을 합쳤을 때 max_subarray

1), 2)는 카데인 알고리즘을 적용하면 되고, 3)은 1)+2)+가운데원소값 으로 구할 수 있다. 

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        def findBestSubarray(nums, left, right):
            # Base case - empty array.
            if left > right:
                return -math.inf

            mid = (left + right) // 2
            curr = best_left_sum = best_right_sum = 0

            # Iterate from the middle to the beginning.
            for i in range(mid - 1, left - 1, -1):
                curr += nums[i]
                best_left_sum = max(best_left_sum, curr)

            # Reset curr and iterate from the middle to the end.
            curr = 0
            for i in range(mid + 1, right + 1):
                curr += nums[i]
                best_right_sum = max(best_right_sum, curr)

            # The best_combined_sum uses the middle element and
            # the best possible sum from each half.
            best_combined_sum = nums[mid] + best_left_sum + best_right_sum

            # Find the best subarray possible from both halves.
            left_half = findBestSubarray(nums, left, mid - 1)
            right_half = findBestSubarray(nums, mid + 1, right)

            # The largest of the 3 is the answer for any given input array.
            return max(best_combined_sum, left_half, right_half)
        
        # Our helper function is designed to solve this problem for
        # any array - so just call it using the entire input!
        return findBestSubarray(nums, 0, len(nums) - 1)

시간 복잡도는 문제 해결 단계수가 N번이지만,
N번당 단계마다 특정 요인에 의해 연산 시간이 줄어들기 때문에 O(N*logN) 이다.