Kadane 알고리즘 최대 부분 배열
각 위치에서 기존 구간을 이어갈지 새로 시작할지 결정합니다.
Kadane 알고리즘 최대 부분 배열이란?
각 위치에서 기존 구간을 이어갈지 새로 시작할지 결정합니다.
합이 가장 큰 연속 구간을 찾습니다.
언제 사용하나요?
- 알고리즘과 자료 구조를 이해합니다.
- 각 단계와 경계 조건을 확인합니다.
- 실행 시간과 메모리 사용량을 비교합니다.
예제 코드
main.py
def maximum_subarray_sum(values):
current = best = values[0]
for value in values[1:]:
current = max(value, current + value)
best = max(best, current)
return best
print(maximum_subarray_sum([-2, 1, -3, 4, -1, 2, 1, -5, 4]))예상 출력
6작동 원리
한 번의 순회로 계산해 시간 O(n), 메모리 O(1)입니다.
값을 변경하고 Python 설치 없이 CodeUtility 온라인 Python 컴파일러에서 실행하세요.
연습 문제
입력값과 경계 조건을 바꾸고 더 큰 데이터에서도 동작을 확인하세요.
- 빈 입력, 한 요소, 중복값을 시험하세요.
- 각 단계의 상태를 출력하세요.
- 다른 풀이와 성능을 비교하세요.