[Algorithm][LeetCode][Easy][Python] 53. Maximum Subarray

Easy 난이도라 만만하게 봤다가 혼났다.

 

딱 이런 부류의 문제를 위한 알고리즘이 있더라.

 

 

문제는 여기서 볼 수 있다.

 

---

 

문제

입력 값으로는 nums라는 배열이 들어오고,

 

배열 안에는 최소 하나의 정수가 존재한다.

 

 

배열 원소들 중 연속되는 subarray의 합이

 

최대가 되는 것을 찾아 return 해야 한다.

 

 

예를 들어,

 

입력값으로 [-2, 1, -3, 4, -1, 2, 1, -5, 4]가 들어오면

 

subarray 중 [4, -1, 2, 1]의 합이 6으로

 

합이 가장 크기 때문에 6을 return 하면 된다.

 

 

편의를 위해 배열의 길이는 N이라 가정한다.

 

 

해결 방법 - (1) Brute Force

누구나 쉽게 생각할 수 있는.

 

흔히 노가다라고 부르는 방법이다.

 

 

너무나 쉬운 방법이므로 따로 코드는 안 남긴다.

 

 

2중 for 문을 돌아야 하기 때문에

 

시간 복잡도는 O(N^2)다.

 

 

해결 방법 - (2) Dynamic Programming - Kadane's Algorithm

우선 Dynamic Programming(DP)와

 

DP 구현 방법 중 하나인 Kadane's Algorithm이

 

무엇인지 알아야 한다.

 

 

Dynamic Programming - Kadane's Algorithm (카데인 알고리즘)

 

 

위 블로그에서 그러한 설명을 아주 잘 해놨다.

 

Kadane's Algorithm

위 글을 참고하여

 

Kadane's Algorithm(카데인 알고리즘)이

 

무엇인지 알아보고,

 

어떻게 이 문제에 적용 가능한지 한 번에 알아보자.

 

 

카데인 알고리즘을 증명하기 위해

 

위에서 언급한 Brute Force 방법을 

 

아래처럼 배열의 끝 부분부터 시작한다고 가정하자.

 

출처) https://sustainable-dev.tistory.com/23

 

A 배열의 5번째 인덱스에 위치한 2에 대해

 

subarray 합이 가장 큰 것을 알아보려면

 

위 그림 오른쪽처럼 찾아보면 된다.

 

 

그다음 순서인 4번째 인덱스에 위치한 -1에 대해

 

subarray 합이 가장 큰 것을 알아보려면

 

위 그림 왼쪽처럼 찾아보면 된다.

 

 

그런데 뭔가 중복되는 것을 볼 수 있다.

 

아래 그림을 보자.

 

출처) https://sustainable-dev.tistory.com/23

 

배열의 i번째 인덱스에 위치한 원소에 대해

 

subarray 합이 가장 큰 것을 알아보려면,

 

 

배열의 i-1번째 인덱스에 위치한 원소에 대해

 

구했던 subarray 합들을 이용하면 알 수 있다.

 

 

정확히는

 

max(A[i], LocalMaximum[i-1] + A [i])가

 

우리가 찾던 답이 될 것이다.

 

Python 코드

사실 이 문제는 LeetCode에서

 

Solution이 무료로 풀려있는 문제여서

 

해당 문제로 가면 볼 수 있다.

 

 

나처럼 그마저 귀찮은 사람을 위해

 

아래 코드를 남긴다.

 

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # Initialize our variables using the first element.
        current_subarray = max_subarray = nums[0]
        
        # Start with the 2nd element since we already used the first one.
        for num in nums[1:]:
            # If current_subarray is negative, throw it away. Otherwise, keep adding to it.
            current_subarray = max(num, current_subarray + num)
            max_subarray = max(max_subarray, current_subarray)
        
        return max_subarray

 

Brute Force와는 달리

 

배열을 딱 한 번만 순회하면 되므로

 

시간 복잡도는 O(N)이다.

 

 

해결 방법 - (3) Divide and Conquer

이 방법은 카데인 알고리즘보다

 

더 느리고 더 많은 공간을 차지한다.

 

 

하지만 한 문제를 여러 방법으로 풀어보는 것이

 

알고리즘 코딩 실력 향상에 중요하기 때문에

 

이 방법에 대해서도 알아본다.

 

Divide and Conquer

출처) https://leetcode.com/explore/learn/card/recursion-ii/470/divide-and-conquer/2897/

 

위 그림으로

 

Divide and Conquer(분할 정복)가 무엇인지

 

한눈에 파악 가능하다.

 

 

말 그대로,

 

어떠한 문제를 작은 문제들로 나누고

 

작은 문제마다 해결책을 찾아

 

각 작은 문제들의 결과를 합친다.

 

 

대표적인 알고리즘으로는

 

Merge Sort와 Quick Sort가 있다.

 

Python 코드

분할 정복 알고리즘을 이 문제에 적용하면

 

정답은 아래 세 가지 결괏값 중

 

가장 큰 것이 될 것이다.

 

 

** 배열의 가운데 원소 기준 **

 

(1) 왼편의 maximum subarray

 

(2) 오른편의 maximum subarray

 

(3) 왼편, 오른편을 합쳤을 때의 maximum subarray

 

 

(1)과 (2)는 배열의 가운데 원소를 포함하지 않고,

 

(3)은 배열의 가운데 원소를 무조건 포함해야 한다.

 

 

(1)과 (2)에서 maximum subarray를 찾을 때

 

위에서 알아본 카데인 알고리즘을 적용하면 되고,

 

(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)

 

시간 복잡도는

 

배열을 한 번 돌고, 

 

반으로 나눈 배열들도 돌아야 하기 때문에

 

O(N * logN)이며,

 

 

공간 복잡도는

 

재귀 함수를 (log N) 번 돌아야 하기 때문에

 

스택에 그만큼 쌓여서

 

O(logN)이 된다.

 

---

 

끝!