[DSA][Greedy] 01. Maximum Subarray

LeetCode 53

 

01. Maximum Subarray

Given an integer array nums, find the subarray with the largest sum, and return its sum.

 

 

[질문하기]

- 배열에 음수나 0이 포함될 수 있나요? YES

 

[아이디어]

- 현재까지의 합이 음수라면 그 값을 유지할 이유가 없으므로 새로운 부분 배열을 시작하는 것이 유리하다.

 

 

[풀이 1] Kadane's Algorithm

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

Kadane's Algorithm은 연속된 부분 배열의 합이 최대가 되는 값을 구할 때 매우 효율적인 알고리즘이다.

현재까지의 최대 부분 합을 추적하면서, 현재까지의 부분 합이 양수이면 그 값을 계속 확장하고, 음수라면 새로운 부분 배열을 시작한다. curSum은 현재까지 탐색한 부분 배열의 합, maxSum은 지금까지 발견한 부분 배열 중 가장 큰 합이다. curSum을 계산할 때 값이 음수라면 새로운 배열을 시작하는 것이 유리하므로 curSum을 갱신한다.

 

 

⏱️ 시간복잡도

배열을 한 번만 순회하므로 시간 복잡도는 O(n)이다.

🧠 공간복잡도

추가적인 공간을 거의 사용하지 않기 때문에 공간 복잡도는 O(1)이다.