[Leetcode][53][Medium] Maximum Subarray

문제

53번 문제 링크

간단한 DP 문제이다.
요약하면, 배열의 부분 배열 중 요소의 합이 가장 큰 부분 배열을 찾는 것이다.
조건이 1 <= s.length <= 10^5 이므로 시간복잡도는 O(N)이 되도록 접근하였다.

풀이

처음은 Memoization

처음 접근은 Memoization을 적용해보고자 하였다.
재귀를 사용하여 i ~ j 범위 값 내의 합과 i+1 ~ j, i ~ j-1 의 각각 합 끼리 비교하며
각 값들을 좌표 기준으로 hash map에 해당 범위 내 최고 합을 저장하는 방법이다.
충분히 최적화되면 각 재귀 당 불필요 호출되는 재귀가 줄어들 것이다 판단하였다.

음… 결과적으로는 시간 복잡도가 O(N^2) 급으로 나오는지 풀리지 않았다…
재귀로 풀면 O(2^N)의 호출이겠으나, Memoization으로 최적화가 된다면
O(N)으로 시간이 단축되리라 생각하였다.
이거는 지금도 가능해보이는데, 최적화를 잘못 시킨게 아닐까 해서 다시 시도해보려고 한다.

• Fibonacci with Memoization

다른 방법을 찾아라

다른 방법을 써서 문제를 해결하였다.
n-1 까지의 합(current_val)을 구하면서 부분 배열의 합을 구한다.
이 때, n번 째 요소를 합했을 때 current_val이 음수가 되는 경우,
n-1 까지의 구간은 전체 합을 감소시키는 원인이 된다.
그러므로 음수가 되는 순간, 지금까지의 요소 합을 0으로 초기화하고 다시 부분 배열의 합을 시작한다.
이 풀이는 Solution을 참고하여 나온 결과이므로, 이후 다시 살펴봐야 한다.

def maxSubArray(self, nums: List[int]) -> int:
        max_val = nums[0]
        current_val = nums[0]
        for n in nums[1:]:
            if current_val < 0:
                current_val = 0
            current_val += n

            max_val = max(current_val, max_val)

        return max_val

회고

1. 풀이는 스쳐지나가듯 보더라도 너무 큰 도움이 된다(안좋다는 뜻 ㅎ).
2. 재귀적으로 풀어보는 것은 한 번 더 Retry 해봐야겠다.
3. 솔루션을 보니 Divide and Conquer로 푸는 법이 있는데 이것도 도전.