[Meetcode-2020-07-18] 53. Maximum Subarray

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

매우 유명한 문제네요.

Brute Force

일단 가장 쉬운 방법은 모든 경우에 대해서 해보는 것 입니다.

시작과 끝을 정하고, subarray 의 합을 구해 봅시다.

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        ret = float('-inf')
        for s in range(len(nums)):
            for e in range(s, len(nums)):
                ret = max(ret, sum(nums[s:e+1]))
        return ret

위의 코드의 시간 복잡도는 O(N^3) 입니다.

prefix sum 을 이용하여서 subarray 의 합을 O(1) 로 구할 수 있습니다.

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        sums = [0]
        for num in nums:
            sums.append(sums[-1] + num)
        ret = float('-inf')
        for s in range(len(nums)):
            for e in range(s, len(nums)):
                ret = max(ret, sums[e+1]-sums[s])
        return ret

Divide and Conquer

이제 조금 더 생각 해 봅시다.

이 배열을 반으로 나눈다고 할 때, 정답은 왼쪽의 배열 또는 오른쪽의 배열 또는 중간을 지나는 배열이라고 생각 할 수 있습니다.

중간을 지나는 배열의 최대 subarray sum 은 어떻게 구할 까요?

중간점이 mid 라고 하고, 최대 sum 을 가지는 subarray 을 nums[l:r+1] 이라고 해봅시다.

그러면 $l \leq mid \leq r$ , $max_l(max_r(\sum_{i=l}^rnum_i))$ 로 우리가 원하는 식을 적을 수 있습니다.

$max_l(max_r(\sum_{i=l}^{mid}num_i + \sum_{i=mid+1}^{r}num_i)) = \\max_l(max_r(\sum_{i=l}^{mid}num_i)) + max_l(max_r(\sum_{i=mid+1}^{r}num_i))$

$max_l(\sum_{i=l}^{mid}num_i)+max_r(\sum_{i=mid+1}^{r}num_i)$ 로 식을 변형할 수 있고, 이것은 쉽게 선형시간으로 구할 수 있습니다.

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

        if len(nums) == 1:
            return nums[0]
				# 모든 숫자가 0 보다 작으면 가장 큰걸 리턴. 최소길이가 1이여야 하기 때문에 
        if all(num < 0 for num in nums):
            return max(nums)
        n = len(nums)
				# 왼쪽, 오른쪽의 sub-problem
        ret = max(0, self.maxSubArray(nums[:n//2]), self.maxSubArray(nums[n//2:]))
				# 중간을 지나는 subarray 의 최대 값.
        l = cur = 0
        for i in range(n//2-1, -1, -1):
            cur += nums[i]
            l = max(l, cur)
        r = cur = 0
        for i in range(n//2, len(nums)):
            cur += nums[i]
            r = max(r, cur)
        ret = max(ret, l+r)
        return ret

Greedy

조금 더 쉽게 생각해 보죠.

우리가 원하는 subarray 가 nums[l:r+1] 이라고 해봅시다.

l ≤ x ≤ r 을 만족하는 x 중에서 sum(nums[l:x])<0 을 만족하는 x 가 존재할 수 있을까요?

sum(nums[l:r+1]) = sum(nums[l:x]) + sum(nums[x:r]) 일 때 만약 sum(nums[l:x])<0 이라면

sum(nums[l:r+1]) < sum(nums[x:r]) 을 만족하게 됩니다.

즉 우리가 정답이라고 생각한 sub array 가 정답이 아니게 되고 모순이 일어납니다. 즉, 우리가 원하는 subarray 에는 위의 조건과 같은 x 는 존재 할 수 없습니다.

이것을 이용해서 구현을 해봅시다.

시간복잡도는 O(N) 이 됩니다.

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        cur = 0
        ret = float('-inf')
        for num in nums:
            cur += num
            ret = max(ret, cur)
            if cur < 0:
                cur = 0
        return ret