LeetCode 풀기 - 53. Maximum Subarray

53. Maximum Subarray

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

Maximum Subarray - LeetCode

문제)

솔루션1) - Brute Force

Brute force로 이중 반복문을 통해서 모든 부분합을 구해서 문제를 풉니다.

시간 복잡도가 O(n^2) 입니다.

너무 느려서 Time Limit Exceeded 에러가 발생합니다.

 

문제의 요구사항은  O(n) 수준으로 문제를 풀어야 합니다.

# Brute-Force Approach
# Time Limit Exceeded
class Solution:
    def maxSubArray(self, nums):
        max_sum = -inf
        for i in range(len(nums)):
            cur_sum = 0
            for j in range(i, len(nums)):
                print(nums[i:j])
                cur_sum += nums[j]
                max_sum = max(cur_sum, max_sum)
        return max_sum

솔루션2) - Kadane's 알고리즘

Dynamic Programming 접근 방식으로 문제를 푸는 알고리즘입니다.

이전 계산된 부분합을 사용하기 때문에 모든 부분합을 처음부터 다시 계산하지 않습니다.

 

Kadane's algorithm 예시, 출처 - https://zerobone.net/blog/cs/kadane-algorithm/

 

시간 복잡도 : O(n)

공간 복잡도 : O(1)

 

이런 방식으로 문제를 풀어나가는 방식을 저는 도저히 생각해 내지 못 했습니다. ㅡㅡ;;

 

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_sum = nums[0]
        cur_sum = nums[0]
        for i in range(1, len(nums)):
            cur_sum = max(cur_sum + nums[i], nums[i])
            max_sum = max(cur_sum, max_sum)
        return max_sum

솔루션3) - 분할 정복 (Divide and Conquer)

문제가 요구한대로 분할 정복 방법을 이용해서 문제를 푸는 방식입니다.

머지 소트 방식과 유사한 형태입니다.

mid를 구하고 왼쪽, 오른쪽으로 나눠서 왼쪽 subrrary에서 최대 부분합, 오른쪽 subrray 최대 부분합을 구하고 그 중에 최대값이 되는 부분합이 구합니다. 왼쪽, 오른쪽에 걸쳐져서 있는 경우가 있을 수 있기 때문에 CrossSum도 추가적으로 구해서 left sum, right sum, cross  sum의 최대값을 구하는 방식입니다.

 

 

Divide and Conquer, 출처 - https://www.learnbay.io/maximum-subarray/

알고리즘 요약

• left_subarray_sum : 왼쪽 subarray의 최대 sum 값
• right_subarray_sum : 오른쪽 subarray의 최대 sum 값
• max_cross_sum : 가운데((left+right)/2)에 걸쳐서 왼쪽, 오른쪽 subarray에 포함되는 영역의 최대 sum 값
• 위 세 개의 솔루션을 머지(위 세 값의 최대 값을 리턴)

시간 복잡도 : O(nlogn)

공간 복잡도 : O(1)

 

class Solution:
    def maxSubArray(self, nums, l=None, h=None):
        if l == None: l = 0
        if h == None: h = len(nums) - 1
        
        if l == h:
            return nums[l]
        
        m = (l + h) // 2
        
        left_subarray_max_sum = self.maxSubArray(nums, l, m)
        right_subarray_max_sum = self.maxSubArray(nums, m+1, h)
        max_cross_sum = self.maxCrossSum(nums, l, m, h)
        
        return max(left_subarray_max_sum, right_subarray_max_sum, max_cross_sum)
        
    def maxCrossSum(self, nums, l, m, h):
        local_sum = 0
        left_sum = -inf
        for i in range(m, l-1, -1):
            local_sum += nums[i]
            left_sum = max(local_sum, left_sum)
        
        local_sum = 0
        right_sum = -inf
        for i in range(m+1, h+1):
            local_sum += nums[i]
            right_sum = max(local_sum, right_sum)
        
        cross_sum = left_sum + right_sum
        return max(left_sum, right_sum,  cross_sum)

 

 

함께 보면 좋을 글:

https://zerobone.net/blog/cs/kadane-algorithm/

Kadane’s algorithm and the idea behind it

https://sustainable-dev.tistory.com/23

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

https://www.geeksforgeeks.org/maximum-subarray-sum-using-divide-and-conquer-algorithm/

Maximum Subarray Sum using Divide and Conquer algorithm - GeeksforGeeks

https://www.learnbay.io/maximum-subarray/

Maximum Subarrays | Divide And Conquer | learnbay.io