LeetCode [53]: Maximum Subarray

📌 LeetCode [53]: Maximum Subarray

🔗 문제 링크

---

문제 설명 📄

배열에서 연속된 부분 배열의 합 중 가장 큰 값을 반환합니다.

---

Solution 💻

from typing import List

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

        for num in nums:
            current_sum = max(num, current_sum + num)
            max_sum = max(max_sum, current_sum) 
        
        return max_sum

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(n)
  • 배열을 한 번 순회하며 최대 부분 배열 합을 계산합니다.

공간 복잡도 분석 🗄️

• 공간 복잡도: O(1)
  • 추가 공간을 사용하지 않고 변수만 사용합니다.