카데인 알고리즘을 활용하면 쉽게 해결할 수 있는 문제이다.
· 카데인 알고리즘
카데인 알고리즘(Kadane's algorithm)은 다이나믹 프로그래밍을 활용한 알고리즘으로, 지금까지 구한 경우의 수 중 최댓값과 현재 원소 값 중 더 큰 값을 중간 최댓값으로 저장하는 것을 반복하는 간단한 문제이다. 말로는 조금 어렵게 느껴질 수 있는데, 아래 그림을 보자.
-1 원소를 포함하는 연속 부분합은 다섯 가지 경우가 있다. 우리는 이 값을 모두 활용하지 않을 것이다. 가장 큰 값만 기억하면 된다.
다섯 가지 경우에 새로운 숫자를 더했을 때 기존의 최댓값은 변함없이 최대일 것이며, 기존 최댓값이 음수일 경우 새로운 원소 자체가 더 큰 값일 수 있으므로 MAX(신규 원소, 기존 최댓값 + 신규 원소)를 최댓값으로 갱신해준다.
카데인 알고리즘을 적용한 코드 전문은 아래와 같다.
int solution(vector<int> &A) {
long long local_max = -1000000;
long long global_max = -1000000;
for(auto ele : A){
local_max = (local_max + ele > ele) ? local_max + ele : ele;
global_max = (local_max > global_max) ? local_max : global_max;
}
return global_max;
}출처
▶ 카데인 알고리즘 예시 이미지 출처
▶ namic Programming - Kadane’s Algorithm (카데인 알고리즘)
