53. Maximum Subarray (Array, Divide and Conquer, Dynamic Programming)

링크 - https://leetcode.com/problems/maximum-subarray/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

1) DP

우리는 one pass를 통해 현재까지의 subarray의 총합을 추적하면서 답을 구할 수 있다.

예를 들어, [-3,-5,1,3,-2,6,1]를 보자. 우리는 아무것도 안하고 0을 반환할 수 없으므로 먼저 -3으로 값을 초기화 한 뒤, list를 두번째 원소부터 돌린다. 그 다음값은 -5이므로, -3-5=-8보다 -5를 가지고 가야한다. 아니면 -3이 계속 subarray의 값을 감소시키기 때문이다.

다시 말해, 우리는 현재 총 subarray합이 음수이면, 그 값을 버리고 다시 시작해야한다.

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

        for num in nums[1:]:
            if cur_sum < 0:
                cur_sum = num
            else:
                cur_sum += num
            # We can do above codes with cur_sum = max(num, cur_sum + num)
            ans = max(ans, cur_sum)

        return ans

Time Complexity: O(n) nums를 돌고있다.

Space Complexity: O(1)

2) Divide and Conquer (Advanced)

우리는 divide and conquer이 시간복잡도와 공간복잡도가 dp보다 낮은걸 알지만, 그래도 인터뷰니까 이렇게 푸는 방법을 물어볼 수 있다.

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)

Time Complexity: O(nlogn)

Space Complexity: O(logn)