[7th batch] week 3 - maximum subarray

liza0525 · liza0525 · commit d433b66411d5 · 2026-03-19T16:05:11.000+09:00
diff --git a/maximum-subarray/liza0525.py b/maximum-subarray/liza0525.py
@@ -0,0 +1,19 @@
+# 7기 풀이
+# 시간 복잡도: O(n)
+#  - nums의 모든 요소를 탐색하기 때문에 nums의 길이에 관련되어 있음
+# 공간 복잡도: O(1)
+#  - 변수 이외에 객체를 쓰지 않았기 때문에 공간 복잡도는 O(1)이다(input 길이와 상관 없음)
+class Solution:
+    def maxSubArray(self, nums: List[int]) -> int:
+        curr_sum = nums[0]
+        max_sum = nums[0]
+
+        for i in range(1, len(nums)):
+            # 1. (현재까지의 합과 i의 요소를 더한 값)과 i의 요소를 서로 비교하여 지금까지의 합을 업데이트한다.
+            #  - 자기 자신만으로도 이전 합들보다 크다면 이전 합들은 의미가 없어짐을 얘기
+            curr_sum = max(nums[i], curr_sum + nums[i])
+
+            # 현재까지의 합과 이전 max 합을 비교하여 업데이트
+            max_sum = max(max_sum, curr_sum)
+
+        return max_sum
