[LeeCode] 53. Maximum Subarray

목표없이 풀다보니 의지가 약해지는 것 같아 'data structure'로 묶인 문제를 풀기로 결정.

https://leetcode.com/study-plan/data-structure/?progress=x0f8sqb1 

Data Structure - Study Plan - LeetCode

 

1일차 array 문제 중 두번 째 문제

실제로 외국계 기업들에서 쓰인 문제라니 급 의욕 뿜뿜

 

subarray의 sum중 가장 큰 값을 찾는 문제.

일단 진짜 단순하게 풀면 n^2 문제가 될 것이다.

 

그렇게 풀었더니 바로 시간 초과^_^;;

 

최대나 최소를 물어본다면 역시나 DP 문제가 아닐까 해서 스터디 중

그러다가 Kadane's algorithm을 알게됨

https://en.wikipedia.org/wiki/Maximum_subarray_problem#Kadane's_algorithm

Maximum subarray problem - Wikipedia

간단하게 설명하면

순차적으로 합해가는 과정 중 합이 음수가 되어버린 sub array는 포함하면 오히려 손해이므로 시작 index를 reset하고 다시 시작하는 방법이다.

 

파이썬 풀이1

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

        cnt_sub = largest_sub = nums[0]
        
        for n in nums[1:]:       
            cnt_sub = max(n, cnt_sub + n)
            largest_sub = max(largest_sub, cnt_sub)

        return largest_sub

시간복잡도는 O(N)으로 매우 좋은 코드로 볼 수 있다.

 

이 문제의 아래쪽에 보면 divide and conquer로 문제를 해결하는 방법도 고민해보라고 쓰여있다.

divide and conquer는 O(NlogN)으로 위의 풀이보다 좋지 않은데 굳이?라고 생각했는데

그 의도를 보니 가끔 인터뷰에서는 다른 방법의 풀이를 또 물어보는 경우가 있다고 한다.....

"더 좋은 풀이는 아니지만 이런 방법도 있겠죠?"라는 식으로 내놓을 풀이도 필요하다는 이야기(잘 풀어도 난리네...)

 

파이썬 풀이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)

 

나누고 지지고 볶고 아주 난리도 아니다....

시간날 때 devide and conquer 공부 한다고 생각하고 차근차근 보는걸로...