* 본 게시글은 [알고리즘 문제 해결 전략] 도서를 참고하여 작성되었습니다. *
1. 무식(...)한 알고리즘
int fastMAXSum(int list[]){
int i, j;
int N = 10, ret = MIN, sum = 0;
for(i=0; i<N; i++){
sum = 0;
for(j=0; j<N; j++){
sum += list[j];
ret = max(ret, sum);
}
}
return ret;
}이건 따로 설명 필요 없을 듯.. 하지만 몇자 적는다면
0번째 인자부터 N번째 인자까지 (1...N) 길이의 최대합 부분을 하나하나 만들어 검사하는 것임. 말 그대로 무식한 방법
2. 분할 정복을 이용한 알고리즘
int fastMAXSum(int list[], int lo, int hi){
int i, j;
int mid = (lo+hi)/2;
int left = MIN, right = MIN, sum = 0;
int single;
if(lo == hi) return list[lo];
for(i = mid; i >= lo; --i){
sum += list[i];
left = max(left, sum);
}
sum = 0;
for(j = mid; j <= hi; ++j){
sum += list[i];
right = max(right, sum);
}
single = max(fastMAXSum(list, lo, mid), fastMAXSum(list, mid+1, hi));
return max(left+right, single);
}일단 전체 List에서 구간이 존재할 수 있는 경우는 크게 두가지이다. 완전히 왼쪽/오른쪽 구간에 치우쳐 있거나, 가운데에 걸쳐 존재하는 경우이다.
첫번째로 왼쪽/오른쪽 중 한 구간에 존재하는 경우이다.
두번째로 중간에 걸쳐서 존재하는 경우이다.
3. 동적 계획법 알고리즘
int fastMAXSum(int list[]){
int N = 10, ret = MIN, psum = 0;
int i;
for(i=0; i<N; ++i){
psum = max(psum, 0) + list[i];
ret = max(psum, ret);
}
return ret;
}일단 유의해야할 것이 있다. 바로 구간의 길이가 제한되어 있지 않은 이상, 1이라도 구간에 포함 시키는 것이 이득이기 때문에 전체 구간 합을 음수로 만들지 않는 음수라면 추가해도 나쁠 것 없다는 점이다. 왜냐면 그 뒤에 양수가 등장해 전체 합을 1이라도 올려줄 수 있기 때문이다.
3, 6, 2 다음으로 -5인 음수가 나온다고 '아.. 그래도 음수는 안넣는게 낫지 않나? 그냥 다 뛰어 넘을까?' 할 필요가 없다는 것이다. -5를 추가한다한들 3+6+2 + (-5) = 6이므로, -5를 품고서라도 3, 6, 2를 챙기는게 더 유리하다. 따라서 이 경우에는 의심하지 않고 subList에 -5를 넣는다. 이것이 max(0, subList[...i-1]) + List[i] 에 해당되는 경우다.
그런데 3, 2, 2 다음으로 -8이 나온다면? 3+2+2 + (-8) = -1. 이전의 subList를 다 더해봤자 7인데 -8을 포함 시키면 3, 2, 2를 추가할 이유가 없다. 열심히 담아봤자 -8 하나로 오히려 전체 합을 깎아먹게 되기 때문이다. 따라서 이때는 -8을 포함한 이전의 subList를 버리고 -8 다음 요소를 첫번째로 subList를 새로 구성해 나가면 된다. 이게 max(0, subList[...i-1]) + List[i] 에 해당되는 경우다.
이해를 돕기 위해 설명은 저렇게 했지만, 알고리즘 자체는 일단 psum에 i번째 항목을 먼저 추가한 뒤, 다음 i+1번째에서 i번째 항목이 추가한 subList를 품고 갈지 버리고 갈지 결정하는 것이다.
1), 2)의 경우를 차례로 정리하면 다음과 같다.
