[Greedy] LeetCode “53. Maximum Subarray“ Python 풀이

문제 링크

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

풀이

• 해당 문제는 그리디 알고리즘(Greedy Algorithm)의 한 종류인 카데인 알고리즘(Kadane’s Algorithm)을 사용해서 해결할 수 있습니다.

• 카데인 알고리즘(Kadane's Algorithm)은 배열에서 연속된 부분 배열의 최대 합을 구하는 효율적인 알고리즘입니다.

• 이 알고리즘은 O(N)의 시간 복잡도를 가지며, 다음과 같은 단계로 진행됩니다.

  1. "현재 합"과 "최대 합"을 -inf(음의 무한대)로 초기화합니다.
  2. 배열을 순회하며 다음 두 가지 경우 중 큰 값을 “현재 합”으로 갱신합니다.
     • 이전 인덱스까지의 “현재 합” + 현재 인덱스의 값
     • 현재 인덱스의 값
  3. “현재 합”이 “최대 합”보다 크면 “최대 합”을 “현재 합”으로 갱신합니다.

• 예를 들어, 배열 [-2, 1, -3, 4, -1, 2, 1, -5, -2, 5]의 경우 다음과 같이 진행됩니다.

  

    초기화: 최대 합 = -inf, 현재 합 = -inf
  
    -2: 현재 합 = max(-2, -inf + (-2)) = -2
    1: 현재 합 = max(1, -2 + 1) = 1
    -3: 현재 합 = max(-3, 1 + (-3)) = -2
    4: 현재 합 = max(4, -2 + 4) = 4, 최대 합 갱신 = 4
    -1: 현재 합 = max(-1, 4 + (-1)) = 3
    2: 현재 합 = max(2, 3 + 2) = 5, 최대 합 갱신 = 5
    1: 현재 합 = max(1, 5 + 1) = 6, 최대 합 갱신 = 6
    -5: 현재 합 = max(-5, 6 + (-5)) = 1
    -2: 현재 합 = max(-2, 1 + (-2)) = -1
    5: 현재 합 = max(5, -1 + 5) = 4

• 따라서, 이 배열에서 연속된 부분 배열의 최대 합은 6입니다.

코드

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        curr_sum = float(-inf)
        max_sum = float(-inf)

        for i in range(len(nums)):
            curr_sum = max(curr_sum + nums[i], nums[i])
            max_sum = max(curr_sum, max_sum)

        return max_sum

참고

• https://wellsw.tistory.com/125