티스토리 뷰

공부/Problem solving

Maximum subarray algorithm (Kadane's algorithm) 유도하기

구사과 2014. 11. 8. 12:14

Maximum Subarray Problem을 선형 시간에 푸는 방법은 다음과 같다.

(원래 0 ~ n-1을 선호하지만, 이번에는 부분합을 써야 해서 1 ~ n으로 배열 인덱스를 설정하겠다.)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <cstdio>
#include <algorithm>
using namespace std;
 
int max_sum(int *a, int n){
    int cmax = 0, res = 0, qmax = *max_element(a+1,a+n+1);
    if(qmax < 0) return qmax;
    for (int i=1; i<=n; i++) {
        cmax += a[i];
        if(cmax < 0) cmax = 0;
        res = max(res,cmax);
    }
    return res;
}
 


이 간단하고 빠른 알고리즘은, 1 ~ x 중의 Maximum Subarray라는 문제를 (1 ~ x-1 중의 Maximum Subarray, ~~ x 까지의 Maximum Subarray) 라는 두가지 부분 문제로 나누어서 문제를 해결한다는 아이디어에서 착안했다고 한다. (Dynamic programming의 일종)

하지만, 난 저걸 처음 볼때도 잘 이해가 안 갔고, 지금도 잘 이해가 안간다.

내 방식대로 유도하고자 한다.


#1. naive (n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <cstdio>
#include <algorithm>
using namespace std;
 
int max_sum(int *a, int n){
    int res = 0;
    for (int i=1; i<=n; i++) {
        int sm = 0;
        for (int j=i; j<=n; j++) {
            sm += a[i];
            res = max(res,sm);
        }
    }
    return res;
}
 




더 이상의 자세한 설명은 생략한다.


2. 부분합 사용 (n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <cstdio>
#include <algorithm>
using namespace std;
 
int max_sum(int *a, int n){
    int b[100005] = {}, res = 0;
    for (int i=1; i<=n; i++) {
        b[i] = b[i-1] + a[i];
    }
    for (int i=1; i<=n; i++) {
        for (int j=i; j<=n; j++) {
            res = max(res,b[j] - b[i-1]);
        }
    }
    return res;
}
 

부분합을 사용해서 이렇게도 표현할 수 있다. 아직은 별로 의미 없다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <cstdio>
#include <algorithm>
using namespace std;
 
int max_sum(int *a, int n){
    int b[100005] = {}, res = 0;
    for (int i=1; i<=n; i++) {
        b[i] = b[i-1] + a[i];
    }
    for (int i=1; i<=n; i++) {
        for (int j=0; j<i; j++) {
            res = max(res,b[i] - b[j]);
        }
    }
    return res;
}
 

더 간단한 표현법.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <cstdio>
#include <algorithm>
using namespace std;
 
int max_sum(int *a, int n){
    int b[100005] = {}, res = 0;
    for (int i=1; i<=n; i++) {
        b[i] = b[i-1] + a[i];
    }
    for (int i=1; i<=n; i++) {
        res = max(res,b[i] - *min_element(b,b+i));
    }
    return res;
}

이제부터 의미가 보이기 시작할 것이다.

res = max(b[i] - b[j]) 라고 할때, i를 고정시켜 놓았을때, b[j]는 0  ~ i-1 까지에서의 최솟값이라는 것을 알 수 있다.

그러면, 우리가 0 ~ 0, 0 ~ 1, 0 ~ 2까지의 최솟값을 계속 중복해서 구하고 있다는 사실이 여기서 드러난다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <cstdio>
#include <algorithm>
using namespace std;
 
int max_sum(int *a, int n){
    int b[100005] = {}, res = 0;
    for (int i=1; i<=n; i++) {
        b[i] = b[i-1] + a[i];
    }
    int minv = 0;
    for (int i=1; i<=n; i++) {
        res = max(res,b[i] - minv);
        minv = min(minv,b[i]);
    }
    return res;
}

여기까지만 해도 AC가 된다.

모든 값이 마이너스일 때의 예외처리가 필요한데, 이 부분은 생략한다.


3. 식 변형 (n)

이제 위 식을 조금 변형시키면 완전한 원래 꼴을 유도할 수 있다.

사실 저 위 식으로도 대부분의 문제는 다 풀수 있어 보이니... 이 부분은 생략해도 무방.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <cstdio>
#include <algorithm>
using namespace std;
 
int max_sum(int *a, int n){
    int res = 0;
    int minv = 0;
    int sum = 0;
    for (int i=1; i<=n; i++) {
        sum += a[i];
        res = max(res,sum - minv);
        minv = min(minv,sum);
    }
    return res;
}
 

이제는 b[i] 배열도 불필요하다. sum이라는 변수 하나만으로 모두 대체할 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <cstdio>
#include <algorithm>
using namespace std;
 
int max_sum(int *a, int n){
    int res = 0;
    int sum = 0;
    int sum_minus_minv = 0;
    for (int i=1; i<=n; i++) {
        sum += a[i];
        sum_minus_minv += a[i];
        res = max(res,sum_minus_minv);
        sum_minus_minv = max(sum_minus_minv,sum-sum);
    }
    return res;
}
sum - minv 값을 저장하는 변수를 잡고, 마지막 줄을 적당히 이항시키면 이러한 식이 나온다.

sum - minv를 sum2라 하겠다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <cstdio>
#include <algorithm>
using namespace std;
 
int max_sum(int *a, int n){
    int res = 0;
    int sum = 0;
    int sum2 = 0;
    for (int i=1; i<=n; i++) {
        sum += a[i];
        sum2 += a[i];
        res = max(res,sum2);
        sum2 = max(sum2,0);
    }
    return res;
}

잘 보면 이제 sum 배열도 안 쓴다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <cstdio>
#include <algorithm>
using namespace std;
 
int max_sum(int *a, int n){
    int res = 0;
    int sum2 = 0;
    for (int i=1; i<=n; i++) {
        sum2 += a[i];
        res = max(res,sum2);
        sum2 = max(sum2,0);
    }
    return res;
}
끝.


'공부 > Problem solving' 카테고리의 다른 글

Festivals In JOI Kingdom (JOI 2012)  (0) 2015.01.18
IOI 2012 - 크래이피쉬 글쓰는 기계  (0) 2014.12.29
트리의 지름 (Diameter of tree)  (5) 2014.11.01
KOI 2014 - 버스  (3) 2014.10.15
STL priority queue 활용법  (21) 2014.09.13
공유하기 링크
댓글
공지사항
최근에 올라온 글
Total
Today
Yesterday