forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathhu6r1s.py
More file actions
31 lines (27 loc) · 1.3 KB
/
hu6r1s.py
File metadata and controls
31 lines (27 loc) · 1.3 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
"""
부분합 활용
dp[0] = nums[0]
dp[1] = dp[0] + nums[1] 와 nums[1] 중 큰 값을 넣는다.
[-2, 1]까지의 합과 [1]까지의 합 중 큰 값을 넣는다고 생각하면 된다.
dp[1] = [1]
dp[2] = dp[1] + nums[2] 와 nums[2] 중 큰 값을 넣는다.
dp[1]에서 [-2, 1]를 선택했다면 [-2, 1, -3]까지의 합과 [1]을 선택했다면 [1, -3]까지의 합 중 큰 값을 선택하게 된다.
dp[2] = [1, -3]
dp[3] = dp[2] + nums[3] 와 nums[3] 중 큰 값을 넣는다.
dp[3]은 [1, -3]에 [4]를 추가하여 [1, -3, 4]까지의 합과 nums[3]인 4를 비교하여 큰 값으로 넣는다.
결국 점화식은 dp[i] = max(dp[i-1] + nums[i], nums[i])가 된다.
시간 복잡도 (Time Complexity):
- dp 배열을 채우기 위해 한 번 순회: O(n)
- dp 배열에서 최댓값을 찾기 위해 한 번 순회: O(n)
→ 총 시간 복잡도: O(n)
공간 복잡도 (Space Complexity):
- dp 배열이 입력 크기만큼 필요: O(n)
→ 총 공간 복잡도: O(n)
"""
def maxSubArray(self, nums: List[int]) -> int:
dp = [0] * len(nums)
dp[0] = nums[0]
for i in range(1, len(nums)):
dp[i] = max(dp[i-1] + nums[i], nums[i])
return max(dp)