[leetcode] 53. Maximum Subarray - Python

🔍 Problem

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

---

📰 문제풀이

• 제한 시간: 20분
• 성공 여부: 성공

---

📃 Solving Process

1. 연속적인 부분 수열의 합이 최대한 큰 경우를 찾아야 한다.
2. nums.length의 최소 길이가 1이기 때문에 dp의 초깃값과 찾으려는 정답 max_sum을 nums[0]으로 초기화한다.
3. 두 번째 자리부터 탐색을 시작하며, 연속합의 정보를 이어받아 올 때, 나 자신과 이전까지의 연속적인 수열의 합을 비교한다.
4. 나를 더하는 것보다 나부터 시작하는 게 더 크다면 dp[i]를 nums[i]로 바꿔준다. 그게 아니라면 이전 연속합의 값에 나 자신을 더한다.
5. max_sum은 매번 이러한 연산의 값 중 제일 큰 값을 비교해 저장한다.

---

💻 Code

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]

        dp = [nums[0]] * len(nums)
        max_sum = dp[0]
        for i in range(1, len(nums)):
            dp[i] = max(dp[i - 1] + nums[i], nums[i])
            max_sum = max(max_sum, dp[i])
        return max_sum

---

⏱ Time Complexity

• 항상 N -1번만큼 확인하기 때문에 O(N)만큼의 시간 복잡도가 소요된다.

---

💾 Space Complexity

• nums.length만큼의 dp 배열이 필요하므로 공간 복잡도 역시 O(N)이다.