Algorithm/Greedy

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

운호(Noah) 2024. 3. 23. 19:32

문제 링크

풀이

  • 해당 문제는 그리디 알고리즘(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

참고