LeetCode 53(Maximum Subarray, Python)

1. 문제 링크 

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

Maximum Subarray - LeetCode

2. 문제 설명

• 정수로 구성된 array가 주어졌을 때, element의 합이 가장 큰 subarray를 찾아서, 그것의 합을 반환
• 예시1) nums = [-2,1,-3,4,-1,2,1,-5,4]일 때, subarray [4,-1,2,1]이 가장 합이 크고, 그것의 합이 6이므로 6을 반환
• 예시2) nums = [5,4,-1,7,8]일 때, subarray [5,4,-1,7,8]의 합이 가장 크고, 그것의 합이 23이므로 23을 반환

3. 기존 풀이

• 어렵지 않아보였는데, 소수 개에 대해 통과가 안되거나, timelimit이 되서 결국 풀지 못했음
• 통과하지 못한 timelimit 풀이의 로직은 아래와 같음
  • 왼쪽 제외, 오른쪽 제외한 것의 재귀와 현재 array sum의 max를 반환하는 구조로 짰고,
  • 종료조건은, max(num)가 음수면 그 값을 반환, min(nums)가 양수면 총 합을 반환, 총 길이가 1이면 그 값을 반환하도록 작성
    • 결국 모든 경우의 수를 다 따지는 것과 유사해서 complexity가 높은, 잘못된 풀이.

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:

        if max(nums) < 0:
            return max(nums)
        elif min(nums) > 0:
            return sum(nums)
        elif len(nums) == 1:
            return nums[0]
    
        l_pop = nums[1:]
        r_pop = nums[:-1]

        return max(self.maxSubArray(l_pop), self.maxSubArray(r_pop), sum(nums))

• 제로_콜라의 풀이
  • [-2,1,-3,4,-1,2,1,-5,4]의 예시를 살펴보자. 최대인 연속 부분 배열은 [4, -1, 2, 1]이다.
  • 이때 그 왼쪽[-2, 1]의 합은 음수임을 알 수 있다.
  • 따라서 왼쪽에서부터 살펴보면서 연속 합이 음수가 되면 버리고 그 다음부터 살펴본다.
  • 아래와 같은 순서로 조사한다.
  • 우선 result 초기 값은 배열의 첫번째 요소인 result = -2
  • [-2]는 음수이므로 버린다. → [1,-3,4,-1,2,1,-5,4]
  • [1]은 양수이므로 result 업데이트(result = 1) 후 확장하여 [1, -3] 조사
  • [1, -3]은 음수이므로 버린다. → [4,-1,2,1,-5,4]
  • [4]는 양수이므로 result 업데이트(result = 4) 후 확장하여 [4, -1] 조사
  • [4, -1]은 양수이므로 result 업데이트(result = 4 그대로) 후 확장하여 [4, -1, 2] 조사
  • [4, -1, 2]은 양수이므로 result 업데이트(result = 5) 후 확장하여 [4, -1, 2, 1] 조사
  • [4, -1, 2, 1]은 양수이므로 result 업데이트(result = 6) 후 확장하여 [4, -1, 2, 1, -5] 조사

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # left와 right를 초기화, 결과값 초기화
        left, right = 0, 0
        result = nums[0]

        # 배열 끝까지 반복
        while right < len(nums):
            # 현재 합 계산
            cur_sum = nums[left]
            result = max(result, cur_sum)
            
            # 현재 합이 양수인 동안 더해가며 최대 합 갱신
            while cur_sum > 0 and right < len(nums)-1:
                right += 1
                cur_sum += nums[right]
                result = max(result, cur_sum)

            # 현재 부분 배열 종료 후 left와 right 업데이트
            left = right + 1
            right = right + 1

        # 최대 부분 배열 합 반환
        return result

 

4. 다른 풀이

• GPT가 알려준 Kadane's Algorithm 코드가 정말 간결해서 놀랐다. 
  • Kadane's Algorithm이란?
    • Dynamic Programming을 적용한 방식 (큰 문제를 작은 문제로 쪼개어 해결하고, 한번 풀었던 문제는 어딘가에 저장해서 반복하여 풀지 않는다) 
    • 그 중, "주어진 array of numbers에서 maximum subarray sum을 찾는" 알고리즘이다. (즉, 이번 리트코드 문제를 푸는 알고리즘)
  • 아래 코드를 보면,  
    
    • 현재 시점에서의 누적된 값을 cur_sum에 저장을 한다.
      • 여기서 cur_sum은 for 문을 돌면서, cur_sum에 i를 더한 값과, i 값 중 max로 값을 업데이트 하는데,
        • 예를 들어 [-2,1]에서 cur_sum이 -2인 상태에서 max(-2+1, 1)로 cur_sum을 업데이트 해준다.
        • 이것의 의미는, 1이 지금까지의 cur_sum(-2)에 1을 더한것보다 크기 때문에, 이전까지의 합을 가져갈 필요가 없음을 의미하고, subarray를 [1]로 업데이트 해주게 된다.
      • 그리고 max_sum은 cur_sum들이 계속 업데이트가 되겠지만, 기존에 저장된 max_sum보다 더 큰 값일 때만 max_sum을 업데이트하면서, 모든 for문을 돌면서 가장 최대 합을 가진 subarray의 값을 반환할 수 있게 된다.
    • 하나의 예시로 생각해보면 [-2,1,-3,4,-1,2,1,-5,4]
      • 초기값으로 cur_sum = max_sum = -2
      • for num in nums[1:]로 리스트를 순회한다.
      • [1]에 대해 1 > -2+1이므로 이전까지의 부분합 [-2]를 버리고 [1]부터 살펴보면 된다.
        • cur_sum = 1, max_sum = 1
      • [-3]에 대해 -3 < 1+(-3)이므로 이전까지의 부분합 [1] 을 이용하여 [1, -3]
        • cur_sum = -2, max_sum = 1
      • [4]에 대해 4 > -2+4이므로 이전까지의 부분합 [1, -3]을 버리고 [4]부터 살펴보면 된다.
        • cur_sum = 4, max_sum = 4
      • [-1]에 대해 -1 < 4+(-1)이므로 이전까지의 부분합 [4]를 이용하여 [4, -1]
        • cur_sum = 3, max_sum = 4
      • [2]에 대해 2< 3+2이므로 이전까지의 부분합 [4, -1]을 이용하여 [4, -1, 2]
        • cur_sum = 5, max_sum = 5
      • [1]에 대해 1< 5+1이므로 이전까지의 부분합 [4, -1, 2]을 이용하여 [4, -1, 2, 1]
        • cur_sum = 6, max_sum = 6
      • [-5]에 대해 -5 < 6+(-5)이므로 이전까지의 부분합 [4, -1, 2, 1]을 이용하여 [4, -1, 2, 1, -5]
        • cur_sum = 1, max_sum = 6
      • [4]에 대해 4 < 1+4이므로 이전까지의 부분합 [4, -1, 2, 1, -5]을 이용하여 [4, -1, 2, 1, -5, 4]
        • cur_sum = 5, max_sum = 6

 

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        
        cur_sum, max_sum = nums[0], nums[0]

        for i in nums[1:]:
            cur_sum = max(i, cur_sum+i)
            max_sum = max(cur_sum, max_sum)
        
        return max_sum

• 리트코드 문제에서 divide and conquer를 이용해서 풀어보라는 내용도 문제 말미에 있었는데, 그와 관련 코드는 아래와 같다.
  • divide and conquer란?
    • "분할 정복"
    • 주어진 문제를 더 단순하고, 비슷한 두개 이상의 하위 문제로 분해하여, 각각을 해결한 후, 그 해를 결합하여 주어진 문제를 해결하는 기본 아이디어.
    • 여기서의 적용? 
      • 분할: 주어진 배열을 두 개의 하위 배열로 나눔. 
      • 왼쪽,오른쪽,중간을 포함한 최대부분 배열 찾기: 왼쪽 부분, 오른쪽 부분, 중간을 포함한 부분 배열 중 최대 값 찾기 
      • 재귀적으로 해결: 이 중 최대 값이 위치한 부분을 찾을 때까지 위 단계를 재귀적으로 반복
      • 결합: 위에서 찾은 값 중 가장 큰 값을 반환

class Solution:
    def maxCSubArray(self, nums, mid):
        # 중간을 기준으로 왼쪽 부분 배열에서의 최대 합 찾기
        s = 0
        ls = rs = float('-inf')
        for i in range(mid - 1, -1, -1):
            s += nums[i]
            ls = max(ls, s)
        
        # 중간을 기준으로 오른쪽 부분 배열에서의 최대 합 찾기
        s = 0
        for i in range(mid, len(nums)):
            s += nums[i]
            rs = max(rs, s)
        
        # 중간을 포함하는 부분 배열에서의 최대 연속 부분 배열 합 반환
        return ls + rs
    
    def maxSubArray(self, nums: List[int]) -> int:
        # 기저 사례 처리
        if len(nums) == 1:
            return nums[0]
        if not nums:
            return 0
        
        # 배열을 중간을 기준으로 두 부분으로 나누기
        mid = len(nums) // 2
        
        # 왼쪽, 오른쪽, 중간을 포함하는 세 경우 중 최대값 반환
        ls = self.maxSubArray(nums[:mid])
        rs = self.maxSubArray(nums[mid:])
        cs = self.maxCSubArray(nums, mid)
        
        return max(ls, rs, cs)

 

5. 배운 점

• Divide and Conquer, Kadane's Algorithm.. 어려웠다. 복습해두기!