[알고리즘] Maximum Subarray + 배열에서 부분 최대합을 구하는 방법

어느 순간 1100 명께서 저의 글을 읽어 주셨습니다. 정말 부족한 글이지만 잘 쓰도록 하겠습니다. 

포인트

• 배열에서 부분합을 구하는 방법은 정말 다양하게 있을 수 있습니다. 먼저 LeetCode 문제를 풀어보고 이어서 다른 것들도 써보는 시간이면 좋겠습니다. 
• 저는 다이나믹 프로그래밍으로 해결을 하였습니다. O(n) 즉, 배열을 전부 순회를 하는 경우 답을 구할 수 있다는 뜻입니다. 
• 값을 계속 저장을 해나가면서 만약 더하려고 하는 값이 0 이하일 경우 0으로 초기화한 후 계속해서 더해나가는 것입니다.

python

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        result = 0
        presum = 0
        # DP 를 이용한 방법
        for index in range(len(nums)):
            presum = max(presum, 0) + nums[index]
            # 기존의 값들을 더해간다. 만약 기존의 값이 0보다 작으면 0
            result = max(presum, result)
        return result

정말 간단하게 문제를 해결하였습니다. (우와) -> 하지만 저는 절대 처음부터 저렇게 생각을 하지 못했습니다. 

알고리즘을 잘하지는 못하지만 알고리즘 푸는 단계는 제가 여태까지 풀어본 바, 2가지 단계를 거칩니다.

1. 일단 해결 <- 사실 해결을 하는 단계도 쉽지가 않습니다. 
2. 최적화

이 문제 또한, 최적화를 생각하시면 좋을 것 같습니다. 최적화라는 용어는 순전히 이를 표현하기 위하여 사용한 용어 입니다. 또한, 최적화라해서 코드 로직이 비슷한 것은 아닙니다.

먼저, 제일 처음 푼 풀이 입니다. 

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        result = 0
        for i in range(n):
            sum = 0
            for j in range(i, n):
                sum+=nums[j]
                result = max(result, sum)

        return result

2 중 for - loop 누가 봐도 O(n^2) 의 시간 복잡도를 가지고 있습니다. 하지만 제일 떠올리기 쉬운 코드라고 생각을 합니다.  이를 또한, 공부하는 중에 Divede and Conquer (분할 정복) 방식으로 해결할 수 있는 방법이 있음을 알았습니다.  분할 정복 방식의 시간 복잡도는 O(nlogn) 입니다

class Solution:
    def part(self, start, end, nums: List[int]) -> int:
        if start >= end:
            return nums[start]

        mid = start + (end - start) // 2
        sum = 0
        left_max = -987654321
        for i in range(mid, start-1, -1):
            sum+=nums[i]
            left_max = max(left_max, sum)
        sum = 0
        right_max = -987654321
        for i in range(mid+1, end+1):
            sum+=nums[i]
            right_max = max(right_max, sum)

        value = max(self.part(start, mid, nums), self.part(mid+1, end, nums))
        return max(left_max+right_max, value)

    def maxSubArray(self, nums: List[int]) -> int:
        return self.part(0, len(nums)-1, nums)

 

이번 부터는 시간 복잡도와 제약 조건을 조금 씩 분석을 하면서 작성을 하려고 합니다. 

감사합니다. 

🧶문서는 항상 수정될 수 있습니다. 비판은 환영합니다.