forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathtaurus09318976.py
More file actions
55 lines (45 loc) · 1.79 KB
/
taurus09318976.py
File metadata and controls
55 lines (45 loc) · 1.79 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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#이 문제는 카데인 알고리즘(Kadane's Algorithm) 문제로
#원래 배열에서 연속된 요소들로만 구성된 최대 부분 배열 합을 찾는 문제임
class Solution:
def maxSubArray(self, nums: List[int]):
#max_sum: 지금까지 발견한 가장 큰 부분 배열의 합
#current_sum: 현재 고려 중인 부분 배열의 합
#위의 둘을 첫번째 요소로 초기화
max_sum = current_sum = nums[0]
#두 번째 요소부터 시작
for num in nums[1:]:
#현재 숫자를 포함한 새로운 부분 배열의 합 계산
current_sum = max(num, current_sum + num)
#num: 현재 숫자만으로 새로운 부분 배열 시작
#current_sum + num: 기존 부분 배열에 현재 숫자 추가
#최대 합 업데이트
max_sum = max(max_sum, current_sum)
return max_sum
# 테스트 케이스
solution = Solution()
# 테스트 1
test1 = [-2,1,-3,4,-1,2,1,-5,4]
print(f"Expected: 6")
print(f"Result: {solution.maxSubArray(test1)}")
# 테스트 2
test2 = [1]
print(f"Expected: 1")
print(f"Result: {solution.maxSubArray(test2)}")
# 테스트 3
test3 = [5,4,-1,7,8]
print(f"Expected: 23")
print(f"Result: {solution.maxSubArray(test3)}")
#시간 복잡도: O(n)
#n = nums의 길이
#for 루프가 배열의 길이만큼 한 번 실행됨
#각 반복에서 수행하는 연산:
#max(num, current_sum + num): O(1)
#max(max_sum, current_sum): O(1)
#따라서 전체 시간 복잡도는 O(n)임
#공간 복잡도: O(1)
#추가로 사용하는 공간:
#max_sum: O(1)
#current_sum: O(1)
#num: O(1)
#입력 크기 n과 무관하게 상수 개수의 변수만 사용
#따라서 공간 복잡도는 O(1)임