카데인 알고리즘으로 subarray 최대합 구하기(동적 프로그래밍)
Kadane’s Algorithm
카데인 알고리즘은 배열에서 연속되는 부분의 최대 합을 찾는 효율적인 알고리즘입니다. 이 알고리즘은 동적 프로그래밍의 한 형태로, 배열을 순회하면서 부분 배열의 최대 합을 계산합니다.
핵심 아이디어
우선 가장 왼쪽에서 시작해 오른쪽으로 이동하는 과정을 기준으로 잡습니다.
- 사용되는 변수
- 지금까지 가장 큰 배열합을 저장해 놓을 변수
- 새롭게 시작한 부분부터 지금까지 배열의 합
-
예제
[1, -4, 3, 5, -1] 배열에서 연속된 배열의 합 중 가장 큰 값을 구하라.
max_score = 지금까지 가장 큰 배열합을 저장해 놓을 변수 max_continue = 새롭게 시작한 부분부터 지금까지 배열의 합
- 현재 위치 1
- max_continue = 1 ([1])
- max_score = 1
- 현재 위치 -4
- max_continue = 0 ([1+(-4)] 음수이므로 0으로 초기화)
- max_score = 1 (1 > 1+(-4)이므로)
- 현재 위치 3
- max_continue = 3 ([3])
- max_score = 3 (3 > 1이므로)
- 현재 위치 5
- max_continue = 8 ([3+5])
- max_score = 8 (8 > 3이므로)
- 현재 위치 -1
- max_continue = 7 ([3+5+(-1)])
- max_score = 8 (8 > 7이므로)
- 현재 위치 1
코드 구현
def solution(n, k, a):
# 기본적으로 왼쪽에서 오른쪽으로 가는 것을 기준으로 잡고 생각
max_continue = 0 # 이어지는 최고값
max_score = 0 # 현재까지 최고값
for i in a:
# 해당 요소가 마이너스 요소라면 굳이 왼쪽에서 오른쪽으로 올 필요 없음
if max_continue+i < 0:
max_continue=0
else: # 만약 플러스 요소라면 추가적으로
max_continue += i
max_score = max(max_score, max_continue)
return max_score