Kadane's Algorithm - 연속하는 부분 배열의 최대값
카데인 알고리즘(Kadane’s Algorithm)을 알아보자.
카데인 알고리즘은 연속하는 부분 배열의 최대값을 O(N)만에 찾을 수 있는 알고리즘이다.
조금 더 쉽게 설명하자면
int[] arr = { -2, -3, 4, -1, -2, 1, 5, -1};
ANSWER is 7: [ 4, -1, -2, 1, 5 ]위와 같은 arr 배열에서 부분 합의 최대값인 7을 O(N), 즉 한 번의 순회만으로 찾을 수 있는 알고리즘이다.
int[] arr = { -2, -3, 4, -1, -2, 1, 5, -1};
///
int maxNum = Integer.MIN_VALUE;
int ret = 0;
boolean flag = true;
for(int i = 0; i < arr.length; i++) {
if(arr[i] >= 0) {
flag = false;
maxNum = Integer.MIN_VALUE;
break;
}
if(maxNum < arr[i]) maxNum = arr[i];
}
if(flag) return maxNum;
for(int i = 0; i < arr.length; i++) {
ret += arr[i];
if(ret < 0) ret = 0;
if(maxNum < ret) maxNum = ret;
}
return maxNum;원리는 단순하다. 계속해서 더해가다가 음수가되면 0으로 바꿔주고 지금까지의 더한 값이 maxNum보다 더 커질 때 maxNum 을 갱신하고 return해주면 된다.
여기서 전처리로 flag 의 return 이유는 모든 배열이 음수일 경우 무조건 0 이 출력되기 때문에, 모두 음수 값일 때에는 배열에서 가장 큰 음수값을 출력해 줘야하기 때문이다. for 문이 진행되면서 변하는 값들은 아래의 표를 참조하면 된다.
간단한 알고리즘이지만 막상 생각하려면 쉽지 않을 수 있는 문제다.
그럼 이만!