[leetcode] Maximum Subarray

Maximum Subarray

나의 접근법

• [2022년 3월 31일] 비슷한 문제를 백준에서 봤을 때 못 풀었는데 또 마주하게 되었다🥲 구간합을 구하는 건 DP로 풀 수 있는데, 여기서 최댓값 구하는 걸 하지 못했다.
• [2022년 5월 07일] 오늘도 못 풀었다. 이전에 풀었던 방식이 나에게 와닿지 못했나보다. 구간합을 최대화할 때는 sliding window를 쓰면 O(N)에 해결할 수 있다.

다른 사람 풀이

브루트포스로 구간을 다 확인하면서 풀 수 있지만 O(N2)이기 때문에 N이 커지면 엄청 느려진다. O(N)으로 풀어보자.

여기서 시작한다. 현위치에서 "current_sum이랑 더하는 게 클까, 혼자 있는 게 클까?"라고 물어보면 된다.

index = 1에서 "-2+1이 더 커, 1 혼자 있는 게 더 커?"라고 물어본다. 이때 -2를 더한 거라면 앞에 있는 값을 연속적으로 더하는 게 되는 것이고, 반대로 혼자있는 게 더 크면 그 index부터 값을 계산하는 것이다.

index = 3에서 4 혼자있는 게 더 커서 여기가 시작점이 되었다.

코드

1) 위의 설명에 해당하는 코드

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_sum = nums[0]
        current_sum = max_sum
        
        for i in range(1, len(nums)):
            current_sum = max(nums[i], current_sum+nums[i])
            max_sum = max(current_sum, max_sum)
        
        return max_sum

2) 구간합을 구했을 때 음수가 나오면 굳이 계산할 때 쓸 필요가 없다.

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        curSum = nums[0]
        maxSum = curSum
        
        for i in range(1, len(nums)):
            if curSum < 0:
                curSum = 0
            
            curSum += nums[i]
            maxSum = max(curSum, maxSum)
        
        return maxSum

참고 자료

• Nick White
• NeetCode