카데인 알고리즘
DP(Dynamic Programming)기법 중 하나로 연속적인 수의 나열에서 최대합 또는 곱을 구하는데 사용된다.
아이디어
[-2, 3, -1, 2]의 숫자가 있다. 이 배열에서 최대 부분합을 구해보자.
[-2, 3, -1, 2]의 최대 부분합을 구하기 위해서는 [-2, 3, -1]의 최대 부분합을 알아야 한다. 이를 알기 위해서는 [-2, 3]의 최대 부분합을 알아야 한다. 마지막으로 [-2]의 최대 부분합을 알아야 한다. 이렇게 큰 집합을 작은 부분 집합으로 나누어서 풀이해 정복하는 DP 기법을 이용한다.
슈도 코드
function kadaneAlgorithm(nums) {
var curSum = 0, max = INT_MIN
// i = 1 부터 nums.length - 1까지 반복
i = 1 to nums.length - 1 {
curSum = Max(curSum, curSum + nums[i]);
max = Max(max, curSum);
}
}