1ilsang

Developer who will be a Legend

Kadane's Algorithm - 연속하는 부분 배열의 최대값

2019-11-11 1ilsangData-Structure & 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 배열에서 부분 합의 최대값인 7O(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해주면 된다.

여기서 전처리로 flagreturn 이유는 모든 배열이 음수일 경우 무조건 0 이 출력되기 때문에, 모두 음수 값일 때에는 배열에서 가장 큰 음수값을 출력해 줘야하기 때문이다. for 문이 진행되면서 변하는 값들은 아래의 표를 참조하면 된다.

cover image

간단한 알고리즘이지만 막상 생각하려면 쉽지 않을 수 있는 문제다.

그럼 이만!