★Maximum Subarray★

LeetCode - The World's Leading Online Programming Learning Platform

★다시 풀어봐야할 문제★ (DP 기본문제에 해당, 문제 접근방식이 잘못된것 같아 해설 참고)

문제 파악 [필수 작성]

문제이해

합이 가장 큰 부분배열의 합을 리턴

제한 조건 확인

무조건 O(n) 또는 O(nlogn) 으로 풀어야한다.

아이디어

두개의 l,r 포인터를 양쪽끝에서부터 하나씩 줄여가면서 dfs 진행
dfs 인자는 l,r,tmp_sum

시간복잡도

자료구조

접근 방법 [필수 작성]

아이디어

코드 구현 [필수 작성]

1차 시도

시간초과

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_sum = float("-inf")
        def dfs(l,r,tmp_sum):
            nonlocal max_sum
            
            if l > r:
                return
            else:
                max_sum = max(max_sum,tmp_sum)
            next_sum_l = tmp_sum - nums[l]
            next_sum_r = tmp_sum - nums[r]
            dfs(l+1,r,next_sum_l)
            dfs(l,r-1,next_sum_r)

        dfs(0,len(nums)-1,sum(nums))

        return max_sum

2차 시도

메모리 초과 → 왜 시간초과 메모리 초과 나는지 탐구 필요

from collections import defaultdict
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_sum = float("-inf")
        cache = defaultdict(bool)
        def dfs(l,r,tmp_sum):
            nonlocal max_sum
            nonlocal cache
            if l > r:
                return
            elif cache[(l,r,tmp_sum)] == True:
                return
            else:
                max_sum = max(max_sum,tmp_sum)
            next_sum_l = tmp_sum - nums[l]
            next_sum_r = tmp_sum - nums[r]
            dfs(l+1,r,next_sum_l)
            dfs(l,r-1,next_sum_r)
            cache[(l,r,tmp_sum)] = True

        dfs(0,len(nums)-1,sum(nums))

        return max_sum

cache 에 대한 로그를 뽑아보면

from collections import defaultdict
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_sum = float("-inf")
        cache = set()
        def dfs(l,r,tmp_sum):
            nonlocal max_sum
            nonlocal cache
            if l > r:
                return
            elif (l,r,tmp_sum) in cache:
                return
            else:
                max_sum = max(max_sum,tmp_sum)
            next_sum_l = tmp_sum - nums[l]
            next_sum_r = tmp_sum - nums[r]
            dfs(l+1,r,next_sum_l)
            dfs(l,r-1,next_sum_r)
            cache.add((l,r,tmp_sum))

        dfs(0,len(nums)-1,sum(nums))
        print(sorted(list(cache)))
        return max_sum

위와 같이 O(n^2) 이 소요되기 때문에 시간초과가 나는 것은 당연하다.

3차 시도 (5분 소요)

해설 코드 아이디어만 힌트 얻어옴

구현은 내 힘으로

Bottom-Up

'''
아이디어
dp 리스트를 누적합형식으로 만들어줄 것임.
이전 값의 최대리스트합이 양수면 데려가고
음수면 그냥 현재 내 값만 들고감
'''

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

        for i in range(len(nums)):
            if i == 0:
                dp_list.append(nums[i])
            else:
                if dp_list[-1] < 0:
                    dp_list.append(nums[i])
                else:
                    dp_list.append(nums[i]+dp_list[-1])

        return max(dp_list)

Top-Down

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_sum = -10**4-1
        def dfs(p,nums):
            nonlocal max_sum
            if p == 0:
                max_sum = max(max_sum,nums[p])
                return nums[p]
            else:
                before = dfs(p-1,nums)
                if before > 0:
                    max_sum = max(max_sum, before + nums[p])
                    return before + nums[p]
                max_sum = max(max_sum, nums[p])
                return nums[p]

        dfs(len(nums)-1,nums)
        
        return max_sum

배우게 된 점 [필수 작성]

자유 형식

질문 [ 필수 X ]

Q1.
2차 시도

위 코드는 시간초과와 메모리초과가 나는것으로 판단됩니다. 시간초과는 통상적으로 2억번 연산에 1초로 계산하는것으로 알고 있습니다. 보통 연산시간이 10초가 넘어가면 시간초과가 나는것을 통상적인 기준으로 알고있는데, 코딩테스트에서 메모리 제한의 경우 통상적인 메모리 제한 범위는 어떻게 되나요?

답변

메모리 제한을 명시적으로 주는 코테 사이트도 있지만 리트코드의 경우 명시적인 메모리 제한을 주지 않습니다. 이런 경우 일반적으로 메가바이트 단위까지는 허용되나 기가바이트 이상은 허용되지 않습니다.